Estructuras de datos dinámicas/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

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 uno 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

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

La desventaja de la versión precedente es que requiere un almacenamiento extra de $\Omega (n)$ . 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

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á $\log _{2}n$ , y como la cantidad de elementos a ser recorridos en cada nivel del árbol es $n$ , el orden de la complejidad del algoritmo será $\Omega (n\log n)$ .

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 $i$ se debe iterar sobre $(n-i)$ elementos.
Deberán realizarse $n$ pasos.

Esto requerirá ${\frac {n^{2}+n}{2}}$ iteraciones: el orden de la complejidad del algoritmo será $O(n^{2})$ .

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 $\Theta (n\log n)$ .