Posted By

josepino on 05/26/11


Tagged

time sort element algorithm bubble execution bigger


Versions (?)

K-Esimo Mayor Elemento - Tiempo de ejecución


 / Published in: C
 

  1. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  2. /* PROGRAMA PRINCIPAL
  3.   Author: JOSE PINO - SANTIAGO TORTORA
  4.  Dado un vector de N numeros reales y un numero entero k, determinar el k-esimo mayo elemento.
  5. Se generan dos tipos de algoritmos diferentes para comparar sus tiempos de ejecución en un tabla.
  6.  
  7. El algoritmo1 (selección_mayor1) se basa en ordenar por el metodo burbuja los valores de mayor a menor,
  8.   de este modo los valores mayores quedaran al inicio del arreglo. Luego se ajusta el puntero para que
  9.   k coincida con la posicion del valor en el arreglo.
  10.  
  11.   El algoritmo2 (selección_mayor2) se basa en ajustando el tope al maximo valor asignado. Por ejemplo, si k=1
  12.   entonces el mayor de todos es el resultado, si es k es otro valor, se ajusta el tope con el resultado maximo obtenido
  13.   en el recorrido anterior del arreglo.
  14.  
  15.  
  16.  
  17. */
  18.  
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <time.h>
  22.  
  23. //////////////Prototipos////////////////////////////
  24. void cargarArreglo (int *A, int tam);
  25. void imprimirKesimos (int *A, int tam, int k);
  26. int seleccion_mayor1 (int *A, int k, int n);
  27. int seleccion_mayor2 (int *A, int k, int n);
  28. ////////////////////////////////////////////////////
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35. //////////////////////////////////////////FUNCION PRINCIPAL///////////////////////////////////////////////////////////////////////////
  36. int main () {
  37.  
  38. system ("cls");
  39. int N;
  40. int k;
  41. int maxValorK = 10; //Cantidad maxima de K para el ejemplo, muestra los top 10 del mayor al menor
  42.  
  43.  
  44. for (N = 1000; N<=10000; N+=1000) { //Cantidad de elementos del arreglo
  45. printf (" N = %d", N); //Imprime en pantalla la cantidad N
  46. printf ("\tAlgoritmo 1 \tAlgoritmo 2");
  47. printf("\n----------------------------------------------\n");
  48. int b[N]; //Dimensiona el arreglo para N valores
  49.  
  50.  
  51. for (k = 1; k<=maxValorK; k++) { //El valor kesimo varia desde 1 a [N] o para el ejemplo hasta [maxValorK]
  52. cargarArreglo(b,N); //Funcion que carga el arreglo de tamaño N con valores random
  53. printf ("K = %d", k); //Imprime en pantalla la cantidad K actual
  54. imprimirKesimos (b, N, k); //Funcion que imprime los kesimos de acuerdo a k y los tiempos respectivos
  55. //printf ("Resultado: %d", seleccion_mayor2 (b,k,N)); Muestra los resultados de acuerdo al kesimo mayor elemento
  56. printf("\n");
  57.  
  58. }
  59. printf("\n\n");
  60. }
  61.  
  62. system ("PAUSE");
  63.  
  64. return 0;
  65.  
  66.  
  67. }
  68. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78. ////////////////////////////////////////////////////////////////////////////////////////////////////////
  79. /*Funciona primero ordenando el arreglo por el metodo burbuja de mayor a menor y luego con un puntero
  80. se ubica en la posición k-esima */
  81.  
  82. int seleccion_mayor1 (int *A, int k, int n) {
  83.  
  84.  
  85.  
  86.  
  87. int i;
  88. int j;
  89. int resultado;
  90. int aux;
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97. //ORDENACION DEL VECTOR POR BURBUJA de mayor a menor
  98. for (i = 0; i<n; i++) {
  99.  
  100. for (j = 0; j<n-1; j++) {
  101.  
  102. if (A[j+1] > A[j]) {
  103. aux = A[j+1];
  104. A[j+1]=A[j];
  105. A[j]=aux;
  106.  
  107. }
  108. }
  109. }
  110.  
  111.  
  112. resultado = (A[k-1]); //El arreglo ya esta ordenado y los mayores se encuentran al inicio, se ajusta el puntero para que k=1 coincida con la posicion 0 del arreglo y asi sucesivamente
  113.  
  114. return (resultado);
  115.  
  116.  
  117. }
  118. ////////////////////////////////////////////////////////////////////////////////////////////////////////
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. ////////////////////////////////////////////////////////////////////////////////////////////////////////
  141. /*Funciona haciendo ejecutando k veces un bucle que ajusta el tope de acuerdo al mayor
  142. encontrado en el recorrido previo*/
  143.  
  144. int seleccion_mayor2 (int *A, int k, int n) {
  145.  
  146.  
  147.  
  148. int tope;
  149. int mayor;
  150. int i;
  151. int j;
  152. int max;
  153. int valorkesimo;
  154. mayor = -999999999;
  155. tope = 99999999;
  156.  
  157.  
  158.  
  159. for (i = 1; i<=k; i++) { //El proceso se hara k veces hasta llegar al k-esimo termino
  160. for (j = 0; j< n; j++) { //Recorrido del vector
  161. if ( ((A[j]) > mayor) && ((A[j])<tope) ) { //Si el valor en la posicion [i] es mayor al "mayor" y menor al tope, se asigna
  162.  
  163. valorkesimo = A[j];
  164. mayor = A[j];
  165. }
  166.  
  167. }
  168. tope = valorkesimo; //Se ajusta el tope al mayor para que el tope de la siguiente pasada sea el valor mayor de la anterior
  169. mayor = -9999;
  170.  
  171. }
  172.  
  173.  
  174.  
  175.  
  176. //printf ("\tPrueba respuesta A2: %d", valorkesimo);
  177. return (valorkesimo);
  178.  
  179. }
  180. ////////////////////////////////////////////////////////////////////////////////////////////////////////
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187. ////////////////////////////////////////////////////////////////////////////////////////////////////
  188. /*Funcion que carga el arreglo con valores aleatorios*/
  189. void cargarArreglo (int *A, int tam) {
  190.  
  191. int i;
  192.  
  193. for (i = 0; i< tam; i++) {
  194. A[i] = rand()%11; //Carga el arreglo con valores aleatorios, para la prueba mod11 carga valores desde 0 a 10
  195. }
  196.  
  197. }
  198. ////////////////////////////////////////////////////////////////////////////////////////////////////
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207. ////////////////////////////////////////////////////////////////////////////////////////////////////
  208. /*Funcion que llama a cada funcion de resolucion, mide el tiempo e imprime los valores medidos*/
  209. void imprimirKesimos (int *A, int tam, int k) {
  210.  
  211.  
  212.  
  213. ///// Inicio de medicion de la primera funcion
  214. float total1,inicio1, final1;
  215. inicio1=clock();
  216. seleccion_mayor1 (A, k, tam); //Llamada a la primera funcion
  217. final1=clock();
  218. total1=(final1-inicio1)/(double) CLOCKS_PER_SEC;
  219. ///// Fin de medicion de la primera funcion
  220.  
  221.  
  222.  
  223. printf (" %f",(total1));
  224.  
  225.  
  226.  
  227. ///// Inicio de medicion de la segunda funcion
  228. float total2,inicio2, final2;
  229. inicio2=clock();
  230. seleccion_mayor2 (A, k, tam); //Llamada a la segunda funcion
  231. final2=clock();
  232. total2=(final2-inicio2)/(double) CLOCKS_PER_SEC;
  233. ///// Fin de medicion de la primera funcion
  234.  
  235. printf (" %f", (total2));
  236. printf (" ");
  237.  
  238.  
  239. }
  240. ////////////////////////////////////////////////////////////////////////////////////////////////////

Report this snippet  

You need to login to post a comment.