Pero bueno tomemos tu algoritmo como valido y comparemoslo frente a otros algoritmos amplia-mente documentados y como serian bubble sort y Quick sort como se comporta
Para ello necesitamos algunas subrutinas que nos midan el tiempo de procesamiento de nuestros algoritmos lamentablemente hacer esto no siempre es muy preciso y depende del sistema operativo y arquitectura de la computadora donde se ejecuten estas pruebas.
La primera prueba que vamos a hacer es con tu algoritmo para ello lo encapsule en una función y decidí tomar algunas muestras
Código
#include <stdio.h> #include<windows.h> #include <time.h> double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b){ LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart; } void rellenarOrdenarDatos(int numeros[],int ordenar[],int tamano){ int i,j,ingreso; for( i=0; i<tamano; i++){ numeros[i]=ingreso; ordenar[i] = 1; if(i>0){ j=0; while(j<i){ if( ingreso < numeros[j] ){ ordenar[j] += 1; } else{ ordenar[i] += 1; } j++; } } } } int main() { const int TAMANO=15000; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); rellenarOrdenarDatos(arreglo,ordenar,TAMANO); QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); return 0; }
Entre las muestras que obtuve fueron estos tiempos en milisegundos
Citar
937.9348
1006.7837
984.6807
917.7779
1013.7831
993.5917
1006.7837
984.6807
917.7779
1013.7831
993.5917
Ahora la prueba con BubbleSort
Código
#include <stdio.h> #include<windows.h> #include <time.h> double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b){ LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart; } void rellenarArreglo(int numeros[],unsigned int tamano){ int i=0; for(i=0; i<tamano; i++) { numeros[i]=r; } } void bubbleSort(int numeros[],int tamano){ int i,j,temp; for (i=1; i<tamano; i++){ for(j=0 ; j<tamano - 1; j++){ if (numeros[j] > numeros[j+1]){ temp = numeros[j]; numeros[j] = numeros[j+1]; numeros[j+1] = temp; } } } } int main() { const int TAMANO=15000; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); rellenarArreglo(arreglo,TAMANO); bubbleSort(arreglo,TAMANO); QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); return 0; }
Utilizando el algoritmo bubble sort el tiempo de procesamiento fue mas alto por ende menos optimo aproximadamente 1500 milsegundos en promedio, en este caso te debo los tiempos exactos
Por ultimo utilize el algoritmo Quick Sort y la diferencia fue abismal
El siguiente codigo es similar al anterior salvo por el metodo de ordenamiento
Código
void qs(int lista[],int limite_izq,int limite_der) { int izq,der,temporal,pivote; izq=limite_izq; der = limite_der; pivote = lista[(izq+der)/2]; do{ while(lista[izq]<pivote && izq<limite_der)izq++; while(pivote<lista[der] && der > limite_izq)der--; if(izq <=der) { temporal= lista[izq]; lista[izq]=lista[der]; lista[der]=temporal; izq++; der--; } }while(izq<=der); if(limite_izq<der){qs(lista,limite_izq,der);} if(limite_der>izq){qs(lista,izq,limite_der);} } void quicksort(int lista[],int n) { qs(lista,0,n-1); } int main() { const int TAMANO=15000; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); rellenarArreglo(arreglo,TAMANO); quicksort(arreglo,TAMANO); QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); return 0; }
Aqui una lista de tiempos obtenidos
Citar
2.1082
2.2769
2.1349
2.1203
2.0972
2.1325
2.2769
2.1349
2.1203
2.0972
2.1325
En promedio 2 mili-segundos el tiempo de procesamiento
En conclusion yo te recomendaria usar une metodo de ordenamiento ya que ademas de que evitas reservar memoria inecesaria el performance es mejor.
SI hay dudas o no estas de acuerdo con algo no dudes en hacermelo saber.
Saludos....