Programacion en C/C++
Algoritmos de ordenamiento - Ordenamiento Rápido (Quicksort) |
Escrito por adrianvaca | ||||||||||||||||||||||||||||||||||
Domingo, 03 de Abril de 2011 00:23 | ||||||||||||||||||||||||||||||||||
Página 5 de 5
1. Descripción. Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:
Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:
Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores. 2. Pseudocódigo en C.
Nombre Procedimiento: OrdRap Parámetros: lista a ordenar (lista) índice inferior (inf) índice superior (sup) // Inicialización de variables 1. elem_div = lista[sup]; 2. i = inf - 1; 3. j = sup; 4. cont = 1; // Verificamos que no se crucen los límites 5. if (inf >= sup) 6. retornar; // Clasificamos la sublista 7. while (cont) 8. while (lista[++i] < elem_div); 9. while (lista[--j] > elem_div); 10. if (i < j) 11. temp = lista[i]; 12. lista[i] = lista[j]; 13. lista[j] = temp; 14. else 15. cont = 0; // Copiamos el elemento de división // en su posición final 16. temp = lista[i]; 17. lista[i] = lista[sup]; 18. lista[sup] = temp; // Aplicamos el procedimiento // recursivamente a cada sublista 19. OrdRap (lista, inf, i - 1); 20. OrdRap (lista, i + 1, sup); Nota:
Esta vez voy a cambiar de lista ;-D 5 - 3 - 7 - 6 - 2 - 1 - 4 Comenzamos con la lista completa. El elemento divisor será el 4: 5 - 3 - 7 - 6 - 2 - 1 - 4 Comparamos con el 5 por la izquierda y el 1 por la derecha. 5 - 3 - 7 - 6 - 2 - 1 - 4 5 es mayor que cuatro y 1 es menor. Intercambiamos: 1 - 3 - 7 - 6 - 2 - 5 - 4 Avanzamos por la izquierda y la derecha: 1 - 3 - 7 - 6 - 2 - 5 - 4 3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí. 1 - 3 - 7 - 6 - 2 - 5 - 4 7 es mayor que 4 y 2 es menor: intercambiamos. 1 - 3 - 2 - 6 - 7 - 5 - 4 Avanzamos por ambos lados: 1 - 3 - 2 - 6 - 7 - 5 - 4 En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18): 1 - 3 - 2 - 4 - 7 - 5 - 6 Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente: 1 - 3 - 2 1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]: 1 - 2 - 3 Al llamar recursivamente para cada nueva sublista (lista[0]-lista[0] y lista[2]-lista[2]) se retorna sin hacer cambios (condición 5.).Para resumir te muestro cómo va quedando la lista: Segunda sublista: lista[4]-lista[6] 7 - 5 - 6 5 - 7 - 6 5 - 6 - 7 Para cada nueva sublista se retorna sin hacer cambios (se cruzan los índices). Finalmente, al retornar de la primera llamada se tiene el arreglo ordenado: 1 - 2 - 3 - 4 - 5 - 6 - 7 Eso es todo. Bastante largo ¿verdad? 4. Optimizando.Sólo voy a mencionar algunas optimizaciones que pueden mejorar bastante el rendimiento de quicksort:
Ventajas:
Desventajas:
La mayoría de los problemas de rendimiento se pueden solucionar con las optimizaciones mencionadas arriba (al costo de complicar mucho más la implementación). Este es un algoritmo que puedes utilizar en la vida real. Es muy eficiente. En general será la mejor opción. Intenta programarlo. Mira el código si tienes dudas. |
Otros artículos | |
Comentarios
Suscripción de noticias RSS para comentarios de esta entrada.