Entre el conjunto de elementos a ordenar se selecciona uno, llamado pivote.
Se colocan todos los elementos a la derecha y a la izquierda del pivote según el criterio de ordenación. De esta forma el elemento pivote estará en su lugar correspondiente del listado.
El paso anterior se repite para cada sub-lista, seleccionando un nuevo pivote. Cuando alguna sub-lista tenga un solo elemento el algoritmo termina.
Complejidad
En el caso en que los pivotes sean un extremo de la lista la complejidad es de O(n2). De media la complejidad del algoritmo es de O(nlogn). Por tanto, la selección del pivote es un paso clave que nos ayudará a mejorar la eficiencia del algoritmo.
Código en Java
public class Quicksort
{
public static void main(String[] args)
{
Quicksort qs = new Quicksort();
int numerosAOrdenar[] = {3,5,1,34,22,1,67,32,78,5};
qs.quickSort(numerosAOrdenar, 0, numerosAOrdenar.length-1);
for(int i=0; i<numerosAOrdenar.length;i++)
{
System.out.print(numerosAOrdenar[i]+", ");
}
}
private void quickSort(int numerosAOrdenar[], int izq, int der)
{
int pivote = numerosAOrdenar[izq];
int i=izq;
int j=der;
int auxiliar;
while(i < j)
{
while(numerosAOrdenar[i] <= pivote && i < j) i++;
while(numerosAOrdenar[j] > pivote) j--;
if (i < j)
{
auxiliar = numerosAOrdenar[i];
numerosAOrdenar[i] = numerosAOrdenar[j];
numerosAOrdenar[j] = auxiliar;
}
}
numerosAOrdenar[izq] = numerosAOrdenar[j];
numerosAOrdenar[j] = pivote;
if(izq < j-1)
{
quickSort(numerosAOrdenar,izq,j-1);
}
if(j+1 < der)
{
quickSort(numerosAOrdenar,j+1,der);
}
}
}
