Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Unidad 4/Algoritmos de ordenamiento
Un algoritmo de ordenamiento recibe como entrada una secuencia de elementos, y devuelve una secuencia con los mismos elementos, en la cual el orden relativo de cada elemento respecto de los demás respeta un criterio dado.
Quicksort
[editar]Quicksort es un algoritmo de ordenamiento que utiliza la técnica 'divide y vencerás'. Consiste en dividir la secuencia a ser ordenada en dos partes, de tal manera que cada unos de los elementos de una de las partes sea mayor o igual a todos los elementos de la segunda parte. Cada una de las partes se divide y se le aplica a su vez este procedimiento recursivamente, hasta llegar a las secuencias unitarias. Al finalizar este procedimiento, la secuencia completa queda ordenada.
Algoritmo
[editar]- Elegir un elemento de la secuencia, llamado pivote.
- Reordenar la secuencia de tal manera que los elementos menores que el pivote aparezcan primero, y los mayores después (el orden de los elementos iguales al pivote no importa).
- Ordenar recursivamente las subsecuencias.
El caso base de esta recursión son las secuencias de un elemento.
El algoritmo se puede expresar de la siguiente forma:
public static Collection quickSort(Collection secuencia) { Collection salida, menores, mayores, iguales; if(secuencia.size() == 1) return; Iterator iteradorSecuencia = secuencia.iterator(); Comparable pivote = obtenerPivote(secuencia); while (iteradorSecuencia.hasNext()) { Comparable elementoActual=(Comparable) iteradorSecuencia.next(); if(pivote.compareTo(elementoActual)<0) mayores.add(elementoActual); else if (pivote.compareTo(elementoActual)>0) menores.add(elementoActual); else iguales.add(elementoActual); } mayores = quickSort(mayores); menores = quickSort(menores); salida.addAll(menores); salida.addAll(iguales); salida.addAll(mayores); return salida; }
Versión de ordenamiento sin espacio de almacenamiento adicional
[editar]La desventaja de la versión precedente es que requiere un almacenamiento extra de . Esto puede evitarse ordenando sobre una misma secuencia:
public static void quickSort(List secuencia, int indiceInferior, int indiceSuperior) { int i=indiceInferior, j = indiceSuperior; if(indiceInferior == indiceSuperior) return; Comparable pivote = obtenerPivote(secuencia); for(;i!=j;) { for(;((Comparable)secuencia.get(i)).compareTo(pivote)<0;i++); for(;((Comparable)secuencia.get(j)).compareTo(pivote)<0;j--); intercambiar(secuencia,i,j); i++; j++; } quickSort(secuencia, indiceInferior, i); quickSort(secuencia, i+1, indiceSuperior); } public static List quickSort(List secuencia) { quickSort(secuencia,0,secuencia.size()); return secuencia; }
Análisis
[editar]En el mejor de los casos, en cada paso se dividirá la secuencia en dos partes, de manera que la profundidad del árbol de llamadas iterativas será , y como la cantidad de elementos a ser recorridos en cada nivel del árbol es , el orden de la complejidad del algoritmo será .
En el peor caso, en cada paso se produce una partición completamente desbalanceada, es decir, queda un solo elemento de un lado, y el resto del otro lado, con lo que las iteraciones seguirán la siguientes reglas:
- En el paso número se debe iterar sobre elementos.
- Deberán realizarse pasos.
Esto requerirá iteraciones: el orden de la complejidad del algoritmo será .
Como para una distribución uniforme de los datos, el caso se asemejará mucho más al primero, se dice que el orden de la complejidad promedio del algoritmo es .