Posted By

josepino on 05/26/11

Tagged

sort

Versions (?)

Last Edited at 05/26/11 02:36pm

Statistics

Viewed 936 times

Favorited by 0 user(s)

Related snippets

K-Esimo Mayor Elemento - Tiempo de ejecuciÃ³n

/ Published in: C

Highlighted TextExpand

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/* PROGRAMA PRINCIPAL 
   Author: JOSE PINO - SANTIAGO TORTORA
 Dado un vector de N numeros reales y un numero entero k, determinar el k-esimo mayo elemento.
	Se generan dos tipos de algoritmos diferentes para comparar sus tiempos de ejecuciÃ³n en un tabla.
	
	El algoritmo1 (selecciÃ³n_mayor1) se basa en ordenar por el metodo burbuja los valores de mayor a menor, 
    de este modo los valores mayores quedaran al inicio del arreglo. Luego se ajusta el puntero para que
    k coincida con la posicion del valor en el arreglo.
    
    El algoritmo2 (selecciÃ³n_mayor2) se basa en ajustando el tope al maximo valor asignado. Por ejemplo, si k=1
    entonces el mayor de todos es el resultado, si es k es otro valor, se ajusta el tope con el resultado maximo obtenido
    en el recorrido anterior del arreglo.
	
	
	
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//////////////Prototipos////////////////////////////
void cargarArreglo (int *A, int tam);
void imprimirKesimos (int *A, int tam, int k);
int seleccion_mayor1 (int *A, int k, int n);
int seleccion_mayor2 (int *A, int k, int n);
////////////////////////////////////////////////////

//////////////////////////////////////////FUNCION PRINCIPAL///////////////////////////////////////////////////////////////////////////
int main () {

system ("cls");	
	int N;
    int k; 	
	int maxValorK = 10;												//Cantidad maxima de K para el ejemplo, muestra los top 10 del mayor al menor

for  (N = 1000; N<=10000; N+=1000) {					//Cantidad de elementos del arreglo
      printf (" N = %d", N);                                //Imprime en pantalla la cantidad N
	  printf ("\tAlgoritmo 1 \tAlgoritmo 2");
	  printf("\n----------------------------------------------\n");
      int b[N];                                                    //Dimensiona el arreglo para N valores
        
   
		for (k = 1; k<=maxValorK; k++) {						//El valor kesimo varia desde 1 a [N] o para el ejemplo hasta [maxValorK]
			cargarArreglo(b,N);									//Funcion que carga el arreglo de tamaÃ±o N con valores random
			printf ("K = %d", k);                               //Imprime en pantalla la cantidad K actual
			imprimirKesimos (b, N, k);							//Funcion que imprime los kesimos de acuerdo a k y los tiempos respectivos
			   //printf ("Resultado: %d", seleccion_mayor2 (b,k,N)); Muestra los resultados de acuerdo al kesimo mayor elemento
            printf("\n");
			
		}
		printf("\n\n");
	}
 
 system ("PAUSE");
 
 return 0;

}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////
/*Funciona primero ordenando el arreglo por el metodo burbuja de mayor a menor y luego con un puntero 
se ubica en  la posiciÃ³n k-esima */

int seleccion_mayor1 (int *A, int k, int n) {

int i;
    int j;
    int resultado;
	int aux;

//ORDENACION DEL VECTOR POR BURBUJA de mayor a menor
	for (i = 0; i<n; i++) {
      
		for (j = 0; j<n-1; j++) {
            
			if (A[j+1] > A[j]) {
			    aux = A[j+1];
				A[j+1]=A[j];
                A[j]=aux;
                   
			}
		}
	}

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

return (resultado);

}
////////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////
/*Funciona haciendo ejecutando k veces un bucle que ajusta el tope de acuerdo al mayor 
encontrado en el recorrido previo*/

int seleccion_mayor2 (int *A, int k, int n) {

int tope;
    int mayor;
    int i;
    int j;
    int max;
    int valorkesimo;       
    mayor = -999999999;	                                          
	tope = 99999999;

for (i = 1; i<=k; i++) {												//El proceso se hara k veces hasta llegar al k-esimo termino
 		for  (j = 0; j< n; j++) {											//Recorrido del vector
			if ( ((A[j]) > mayor)  &&  ((A[j])<tope) ) {		//Si el valor en la posicion [i] es mayor al "mayor" y menor al tope, se asigna
				
                valorkesimo = A[j];										
				mayor = A[j];				
			}
			
		}
		tope = valorkesimo;												//Se ajusta el tope al mayor para que el tope de la siguiente pasada sea el valor mayor de la anterior
		mayor = -9999;
		
	}

//printf ("\tPrueba respuesta A2: %d", valorkesimo);
 return (valorkesimo);

}
////////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////
/*Funcion que carga el arreglo con valores aleatorios*/
void cargarArreglo (int *A, int tam) {

int i;

for (i = 0; i< tam; i++) {
		A[i] = rand()%11;         //Carga el arreglo con valores aleatorios, para la prueba mod11 carga valores desde 0 a 10
	}

}
////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////
/*Funcion que llama a cada funcion de resolucion, mide el tiempo e imprime los valores medidos*/
void imprimirKesimos (int *A, int tam, int k) {

///// Inicio de medicion de la primera funcion
    float total1,inicio1, final1;
    inicio1=clock();
       		seleccion_mayor1 (A, k, tam);           //Llamada a la primera funcion
    final1=clock();
    total1=(final1-inicio1)/(double) CLOCKS_PER_SEC;
    ///// Fin de medicion de la primera funcion

printf ("           %f",(total1));

///// Inicio de medicion de la segunda funcion
    float total2,inicio2, final2;
    inicio2=clock();
		   seleccion_mayor2 (A, k, tam);           //Llamada a la segunda funcion
    final2=clock();
    total2=(final2-inicio2)/(double) CLOCKS_PER_SEC;
    ///// Fin de medicion de la primera funcion

printf ("           %f", (total2));
	printf ("     ");

}
////////////////////////////////////////////////////////////////////////////////////////////////////

Report this snippet Tweet