/* Este programa forma parte del Curso de C Copyright (C) 1991 Grupo Editorial Jackson Todos los derechos reservados */ /* ORDENA: comparaci¢n entre varias t‚cnicas de ordenaci¢n */ /* Este programa se linka con la librer¡a de consola de Jackson, utilizando el fichero ORDENA.PRJ para Turbo C 2.0, u ORDENA.MAK para Quick C 2.0. */ #include #include #include #include "Jconio.h" /* prototipos de funciones: */ void ExtraeDatos(double d[], int n); void MuestraDatos(double d[], int n); void Seleccion(double d[], int n); void Insercion(double d[], int n); void BubbleSort(double d[], int n); void ShellSort(double d[], int n); void Quicksort(double d[], int n); int Compara(double *d1, double *d2); void PulseReturn(void); /******************************************************************** * main ********************************************************************/ main() { enum { NDATOS = 200 }; /*n£mero datos a reordenar*/ enum { F1 = 1059, F2, F3, F4, F5, F6 }; /*c¢digos teclas <1>*/ double datos[NDATOS]; /*datos a reordenar <2>*/ clock_t inicio,fin; /*tiempo inicial, final <3>*/ char buf[80]; int c,ok,terminado; srand( (unsigned int)time(NULL)); /*inicia random*/ Jcursor(0); /*elimina cursor*/ do { Jclrscr(); /*borra pantalla*/ Jclrkey(); /*y buffer teclado*/ Jputs("\r\n\n\n\n- Comparaci¢n entre t‚cnicas de ordenaci¢n -\r\n\n" " F1) Ordenaci¢n por selecci¢n\r\n" " F2) Ordenaci¢n por inserci¢n\r\n" " F3) Burbuja\r\n" " F4) Shell\r\n" " F5) Quicksort\r\n" " F6) Salir\r\n\n" "Seleccione F1..F6: "); do { /*lee tecla v lida*/ c = Jgetkey(1); ok = (c >= F1 && c <= F6); /*(est n en orden) <4>*/ if (! ok) Jputch('\a'); } while (! ok); terminado = (c == F6); if (! terminado) { ExtraeDatos(datos,NDATOS); /*datos a reordenar*/ Jclrscr(); /*los imprime*/ Jputs("Extracci¢n aleatoria de datos para ordenar:\r\n\n"); MuestraDatos(datos,NDATOS); Jclrscr(); inicio = clock(); /*tiempo inicial*/ if (c == F1) { /*ejecuta ord. elegida*/ Seleccion(datos, NDATOS); } else if (c == F2) { Insercion(datos,NDATOS); } else if (c == F3) { BubbleSort(datos,NDATOS); } else if (c == F4) { ShellSort(datos,NDATOS); } else if (c == F5) { Quicksort(datos,NDATOS); } fin = clock(); /*tiempo final <5>*/ sprintf(buf,"ejecutado en %3.2f segundos.\r\n\n", ((double)(fin-inicio))/CLK_TCK); Jputs(buf); MuestraDatos(datos,NDATOS); /*imprime datos en orden*/ } } while (! terminado); Jclrscr(); /*borra pantalla*/ Jcursor(1); /*muestra cursor*/ } /* Notas sobre main: <1> Como los c¢digos de las teclas indicadas son n£meros progresivos, basta con asignar el primero. enum se ocupa despu‚s autom ticamente de asignar valores crecientes (1060,1061,...) a las siguientes constantes. <2> Utilizamos un array de double porque la reordenaci¢n de un array int es demasiado r pida. Las comparaciones y asignaciones de double dan una mejor idea del comportamiento t¡pico en condiciones reales. <3> Utilizamos clock en vez de time para obtener una mayor resoluci¢n (cerca de 1/18.2 segundos en los PC). La funci¢n time tiene, sin embargo, y siempre en los IBM PC y compatibles, una resoluci¢n t¡pica de un segundo. <4> Funciona porque los c¢digos de las teclas F1..F6 son n£meros enteros progresivos (ver nota 1). <5> Dividiendo el tiempo empleado para la constante CLK_TCK (definida en ), se obtiene el tiempo en segundos. Recuerde el uso de (double) para asegurar que la divisi¢n se ejecute en double, evitando el riesgo de una divisi¢n entera que perder¡a la parte fraccionaria (dependiendo de como est‚ definido CLK_TCK, es mejor no arriesgarse y utilizar double). */ /******************************************************************** * ExtraeDatos: extrae n enteros casuales en el array d[]. ********************************************************************/ void ExtraeDatos(double d[], int n) { int i; for (i = 0; i < n; i++) { /*en cada elemento*/ d[i] = rand()/100.0; /*un double casual <1>*/ } } /* Notas sobre ExtraeDatos: <1> Pone dos cifras decimales s¢lo con fines est‚ticos: los valores de los datos no interesan, basta que vengan ordenados correctamente. */ /******************************************************************** * MuestraDatos: muestra los n enteros contenidos en el array d[]. ********************************************************************/ void MuestraDatos(double d[], int n) { int i; char buf[80]; for (i = 0; i < n; i++) { /*por cada elemento*/ sprintf(buf,"%7.2f",d[i]); /*imprime en 7 espacios*/ if(Jposx() > 72) { /*a sig. l¡n. si no est */ Jputs("\r\n"); } Jputs(buf); /*muestra dato*/ } Jputs("\r\n"); PulseReturn(); /*espera un Return*/ } /******************************************************************** * Seleccion: reordena por selecci¢n el array d[] de n elementos. ********************************************************************/ void Seleccion(double d[], int n) /*<1>*/ { int i,j,imin; double temp; Jputs("Ordenaci¢n por selecci¢n en curso..."); for (i = 0; i < n; i++) { /*para cada n£mero*/ imin = i; /*¡ndice m¡nimo de i <2>*/ for (j = i+1; j < n; j++) { if (d[j] < d[imin]) { /*recuerda ¡ndice m¡nimo*/ imin = j; } } temp = d[i]; /*intercamb. con m¡n. <3>*/ d[i] = d[imin]; d[imin] = temp; } } /* Notas sobre Selecci¢n: <1> A partir del primer elemento del array, se selecciona el elemento de valor m s bajo y se coloca en primer lugar, intercambi ndolo con el que estaba en primer lugar; despu‚s se avanza i al segundo elemento, se busca el nuevo m¡nimo y se intercambia con el segundo, etc‚tera. En la pr ctica, se seleccionan los elementos uno cada vez en orden creciente, y se colocan a partir del inicio del array. <2> imin es el ¡ndice del elemento de valor m s bajo entre los que ya hay para ordenar. Para buscar el elemento de valor m s bajo, se supone que es el primero (imin = i). Si despu‚s encuentra uno m s bajo, se cambia imin de forma que contenga el ¡ndice del elemento m s bajo. <3> Para el intercambio es necesaria una variable intermedia: el C no tiene instrucciones para intercambiar dos variables, y una funci¢n ser¡a demasiado ineficaz. */ /******************************************************************** * Insercion: reordena por inserci¢n el array d[] de n elementos. ********************************************************************/ void Insercion(double d[], int n) /*<1>*/ { int i,j; double z; Jputs("Ordenaci¢n por inserci¢n en curso..."); for (i = 1; i < n; i++) { z = d[i]; /*n£m. a insertar <2>*/ j = i; /*busca hacia atr s*/ while (j > 0 && d[j-1] > z) { /*<3>*/ d[j] = d[j-1]; /*hace sitio <4>*/ j--; } d[j] = z; /*inserta*/ } } /* Notas sobre Inserci¢n: <1> Cada elemento se inserta en el lugar adecuado entre los ya ordenados. Al principio se considera ordenado s¢lo el primer elemento, por lo que se parte del segundo. Cada elemento se inserta como cuando se ordena una mano de cartas de una baraja. <2> z es el valor a insertar en el lugar adecuado entre los anteriores. <3> Vuelve hacia atr s entre los elementos ya ordenados hasta que no encuentra uno menor o igual a z. z puede insertarse por lo tanto justo despu‚s del elemento encontrado. Recuerde que si la primera condici¢n (j > 0) no es cierta, la segunda ni siquiera se prueba, evitando as¡ acceder a un elemento inexistente del array d[]. <4> Mientras va hacia atr s, coloca delante los elementos aprovechando el lugar en el que estaba z. De este modo, cuando encuentra el lugar adecuado s¢lo debe escribir en ‚l z (el contenido original ya se ha colocado delante). */ /******************************************************************** * BubbleSort: reordena por intercambios el array d[] de n elementos. ********************************************************************/ void BubbleSort(double d[], int n) /*<1>*/ { int i,intercambio; double temp; Jputs("Ordenaci¢n por burbuja en curso..."); do { intercambio = 0; for (i = 1; i < n; i++) { /*explora por pares*/ if (d[i] < d[i-1]) { temp = d[i]; d[i] = d[i-1]; d[i-1] = temp; intercambio = 1; /*e indica <2>*/ } } } while (intercambio); /*sale si no intercambia*/ } /* Notas sobre BubbleSort: <1> A partir del primer par de elementos, el array se explora comparando pares de elementos adyacentes. Si no est n bien ordenados, se intercambian entre ellos. Se repite el procedimiento hasta que en una pasada no se realiza ning£n intercambio, porque los elementos est n todos en orden. <2> El flag (variable l¢gica) intercambio sirve para indicar que se ha realizado al menos un intercambio, y por ello se debe dar otra pasada. */ /******************************************************************** * ShellSort: reordena por Shell sort el array d[] de n elementos. ********************************************************************/ void ShellSort(double d[], int n) /*<1>*/ { int dist; /*distancia entre los elementos a ordenar en una pasada*/ int i,j; double z; Jputs("Ordenaci¢n Shell en curso..."); for (dist = 1; dist < n; dist = dist*3+1) /*distancia inicial <2>*/ ; while ( (dist = dist/3) > 0) { /*hasta distancia 1*/ for (i = dist; i < n; i++) { /*<3>*/ z = d[i]; /*n£m. a insertar*/ j = i; /*busca hacia atr s*/ while (j-dist >= 0 && d[j-dist] > z) { d[j] = d[j-dist]; /*hace sitio*/ j -= dist; } d[j] = z; /*inserta*/ } } } /* Notas sobre ShellSort: <1> Se realiza una ordenaci¢n por inserci¢n considerando s¢lo un elemento cada dist elementos, partiendo con dist bastante grande. Esto coloca r pidamente hacia los extremos los elementos que tienen que moverse mucho para lograr colocarse en su lugar adecuado. dist se reduce despu‚s gradualmente hasta 1, es decir, a una ordenaci¢n por inserci¢n, que sin embargo es rapid¡sima, porque los elementos est n ya en sus lugares correctos. <2> Una secuencia particularmente eficaz para dist es (al rev‚s) la serie 1, 4, 13, 40, 121, ... (multiplica por tres y a¤ade uno). Observe que todo el trabajo se hace en la misma for: la instrucci¢n dependiente de for es una instrucci¢n vac¡a. <3> El ciclo interno es una ordenaci¢n normal por inserci¢n, s¢lo que se considera £nicamente un elemento cada dist. */ /******************************************************************** * Quicksort: reordena con Quicksort el array d[] de n elementos. ********************************************************************/ void Quicksort(double d[], int n) { Jputs("Ordenaci¢n Quicksort en curso..."); qsort(d,n,sizeof(d[0]), (int(*)(const void*, const void*)) Compara); /*<1>*/ } /***** Compara: compara dos elementos, por Quicksort. *****/ int Compara(double *d1, double *d2) { if (*d1 > *d2) return 1; /*<2>*/ else if (*d1 < *d2) return -1; else return 0; } /* Notas sobre Quicksort: <1> En este complejo programa se declara que Compara es un puntero a una funci¢n que recibe dos punteros a void y devuelve un int. Es necesario con los compiladores 100% ANSI porque la funci¢n de librer¡a qsort no puede conocer con anticipaci¢n el tipo exacto de los argumentos que debe pasarle a la funci¢n de comparaci¢n, y por ello los declara como punteros a void. El programa finje que los argumentos son del tipo deseado por qsort, aunque en realidad sean de otro tipo (en este caso, se trata de punteros a double). Obviamente, haci‚ndolo de esta forma se impide al compilador que controle la exactitud de la llamada; por ello es necesario prestar mucha atenci¢n. Como alternativa, se podr¡a modificar la declaraci¢n de Compara utilizando void* y efectuando en su interior los pasos de void* a double*. <2> No se puede hacer simplemente *d1-*d2, porque el valor devuelto por la funci¢n debe ser un int: se perder¡a la parte fraccionaria y n£meros como 12.47 y 12.34 (distintos s¢lo en su parte fraccionaria) ser¡an considerados iguales. De este modo, entre otras cosas, la ejecuci¢n es m s r pida. Se aceptan tres return, ya que dadas las exiguas dimensiones de la funci¢n, no hay problemas de legibilidad. */ /******************************************************************** * PulseReturn: espera una tecla Return. ********************************************************************/ void PulseReturn(void) { Jclrkey(); Jputs("\r\nPulse Return para continuar: "); while (Jgetkey(1) != '\r') { Jputch('\a'); } }