QuickSort es un algoritmo de ordenamiento muy eficiente. Es de naturaleza recursiva y utiliza la filosofía divide y vencerás.
La idea principal de QuickSort es hacer que el conjunto de elementos que se desea ordenar cuente con una característica especial: El arreglo debe tener un elemento δ que se encuentre en su posición final. Todos los elementos menores a δ están a su izquierda y todos los elementos mayores a δ están a su derecha.
Este elemento δ servirá como pivote que indica donde debe ser realizada la división del arreglo.
Sin embargo, es muy improbable encontrar dicha característica en todos los arreglos. Peor aún, resulta muy costoso comprobar si un arreglo dado posee la propiedad. Por lo tanto, en lugar de buscar un pivote natural, elegimos un elemento al azar (para evitar mayores complejidades al elegir un pivote) y reordenamos el arreglo alrededor de dicho elemento de forma tal que cumpla con nuestras necesidades.
Algoritmo básico:
QuickSort(arr[], int left, int right) {
if ((right - left) >= 1) {
int i = split(arr, left, right);
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
}
}
split(arr[], int left, int right) {
int i = left;
int v = random();
swap(arr, left, v);
for (int j = left; j <= right; j++) {
if (arr[j] < arr[i]) {
swap(arr, i, j);
i++;
swap(arr, i, j);
}
}
return i;
}
Nota: Algunas funciones están omitidas debido a que son muy sencillas de implementar y no son centrales para el funcionamiento del algoritmo QuickSort.
Actualización: Código funcional en Java. Esta pequeña aplicación implementa el algoritmo antes descrito y contiene una comparación de desempeño con la implementación del API. Sorprendentemente nuestro algoritmo tan básico solo es 4 veces más lento que el de Java 5.
Leave a Reply