Implementando el algoritmo QuickSort
Desde que existe la ciencia de la computación, uno de los mayores problemas con los que los ingenieros se encontraban en su día a día, era el de ordenar listas de elementos. Por su causa, diversos algoritmos de ordenación fueron desarrollados a lo largo de los años y siempre existió un intenso debate entre los desarrolladores sobre cual de todos los algoritmos de ordenación era el más rápido.
El debate finalizó abruptamente en 1960 cuando Sir Charles Antony Richard Hoare, nativo de Sri Lanka y ganador del premio Turing en 1980, desarrolló el algoritmo de ordenación QuickSort casi por casualidad mientras ideaba la forma de facilitar la búsqueda de palabras en el diccionario.
El algoritmo QuickSort se basa en la técnica de “divide y vencerás” por la que en cada recursión, el problema se divide en subproblemas de menor tamaño y se resuelven por separado (aplicando la misma técnica) para ser unidos de nuevo una vez resueltos.
Características del Algoritmo QuickSort
En la práctica, es el algoritmo de ordenación más rápido conocido, su tiempo de ejecución promedio es O(n log (n)), siendo en el peor de los casos O(n2), caso altamente improbable. El hecho de que sea más rápido que otros algoritmos de ordenación con tiempo promedio de O(n log (n)) ( como SmoothSort o HeapSort ) viene dado por que QuickSort realiza menos operaciones ya que el método utilizado es el de partición.
Explicación abstracta del funcionamiento de QuickSort
- Se elige un elemento v de la lista L de elementos al que se le llama pivote.
- Se particiona la lista L en tres listas:
- L1 – que contiene todos los elementos de L menos v que sean menores o iguales que v
- L2 – que contiene a v
- L3 – que contiene todos los elementos de L menos v que sean mayores o iguales que v
- Se aplica la recursión sobre L1 y L3
- Se unen todas las soluciones que darán forma final a la lista L finalmente ordenada. Como L1 y L3 están ya ordenados, lo único que tenemos que hacer es concatenar L1, L2 y L3
Aunque este algoritmo parece sencillo, hay que implementar los pasos 1 y 3 de forma que se favorezca la velocidad de ejecución del algoritmo.
Eligiendo el Pivote
La velocidad de ejecución del algoritmo depende en gran medida de como se implementa este mecanismo, una mala implementación puede suponer que el algoritmo se ejecute a una velocidad mediocre o incluso pésima. La elección del pivote determina las particiones de la lista de datos, por lo tanto, huelga decir que esta es la parte más crítica de la implementación del algoritmo QuickSort. Es importante intentar que al seleccionar el pivote v las particiones L1 y L3 tengan un tamaño idéntico dentro de lo posible.
Elegir el primero o el último de la lista nunca es una buena idea ya que los elementos de la lista no están uniformemente distribuidos. Por otro lado, si contamos con un buen generador de números aleatorios, podemos elegir un pivote al azar de entre todos los elementos de la lista. Esta estrategia es segura puesto que es improbable que un pivote al azar de como resultado una partición mala, pero tiene como contrapartida que en algunas ocasiones si puede arrojar un resultado de O(n2), además, la elección de números aleatorios puede incrementar el tiempo de ejecución del algoritmo.
Una buena estrategia para solucionar la selección del pivote ámpliamente extendida es la conocida como “a tres bandas”. En esta estrategia lo que se persigue es hacer una media con los valores de tres de los elementos de la lista. Por ejemplo si nuestra lista es [ 8, 4, 9, 3, 5, 7, 1, 6, 2 ] la media sería ( 8 + 2 + 5 ) / 3 = 5 lo que daría lugar a las siguientes particiones:
- L1 = [ 8, 9, 7, 6 ]
- L2 = [ 5 ]
- L3 = [ 1, 2, 4, 3 ]
Esta estrategia no nos asegura que siempre nos dará la mejor selección del pivote, sino que estadísticamente, la elección del pivote sea buena.
Implementando la estrategia de Particionado
Recordemos que el fin de esta implementación de QuickSort es la de crear un algoritmo de ordenación eficiente y rápido, por lo que las listas “auxiliares” que creamos al particionar no son listas reales, es decir, no creamos nuevos elementos de lista para albergar los elementos, sino que situamos el pivote en una posición determinada dentro de la lista para simular las particiones. La mejor opción a la hora de crear las listas que contendrán a L1 y L3 es reordenar los elementos de forma que los elementos que aparecen antes del pivote sean menores o iguales a él, y los que aparecen después sean mayores o iguales.
Eso puede implementarse en Python de la siguiente forma, que además es muy elegante:
def quicksort(L):
# elegimos el pivote
if len(L) > 2: v = L[0] + L[len(L)-1] + L[len(L)-1/2] / 3
elif len(L) == 2: v = L[0] + L[1] / 2
else: v = L[0]
return quicksort(filter((lambda y: y<v ), L)) + [v] + quicksort(filter((lambda y: y>=v), L))
En PHP seria algo así:
<?php
/**
* Array quickSort($arreglo, $campo) ordena un $arreglo en funcion de un $campo
*
* @param tipo $arreglo a ordenar, en funcion de un $campo, desde $inicio asta $final
* @return $regresa el mismo arreglo pero ordenado
* @access publico
* @link: http://es.wikipedia.org/wiki/Quicksort
* -----------------------------Estado pendiente, muy pendiente!!!...----------------------------
*/
function quickSort($arreglo, $campo, $inicio=0,$final=0){
$p=$final;//posicion del pivote sera la final
$i=$inicio;//posicion inicial a ordenar
if($p==0)//caso inicial ';¬)
$p=count($arreglo)-1;
if($p-$i>0){//si observamos el arreglo mas pequeño que puede recibir es de 2 donde $j==$i
$j=$p-1;
for(; $i<$j; $i++){
if($arreglo[$i][$campo] <= $arreglo[$p][$campo])
continue;
if($arreglo[$j][$campo] >= $arreglo[$p][$campo]){
--$i; --$j;
continue;
}
$aux=$arreglo[$i];
$arreglo[$i]=$arreglo[$j];
$arreglo[$j]=$aux;
}
//el elemento p debe de ir en la posicion $i
$valor_pivote = $arreglo[$p];
for(; $i<$p; $i++)
$arreglo[$i+1]=$arreglo[$i];
//finalmente en $j donde todavia esta el valor de i ponemos el valor del pivote
$arreglo[$j]=$valor_pivote;
//chicharronera recursiva mandamos ordenar tanto la parte alta y la baja
$arreglo=$this->quickSort($arreglo, $campo, $inicio, $j-1);
$arreglo=$this->quickSort($arreglo, $campo, $j+1, $p);
}
return $arreglo;
}
Aunque este método funciona perfectamente, existe un método mucho más recomendable puesto que ha demostrado ser más efectivo. Se utilizan dos índices; i o índice izquierdo y j o índice derecho, y se recorre la lista de forma simultánea por ambos índices. Desde el primer elemento usando el índice i y desde el último elemento usando el índice j. Cuando el valor del índice i sea mayor que el del pivote y el valor del índice j sea menor, los elementos son intercambiados en esas posiciones. Ese proceso se repite hasta que los dos índices se cruzan en el mismo elemento, ese punto es la posición correcta del pivote.
¿Confuso?. No te preocupes que todo queda mucho más claro con un ejemplo completo, como no, en Python:
def quicksort(L, first, last):
# definimos los índices y calculamos el pivote
i = first
j = last
pivote = (L[i] + L[j]) / 2
# iteramos hasta que i no sea menor que j
while i < j:
# iteramos mientras que el valor de L[i] sea menor que pivote
while L[i] < pivote:
# Incrementamos el índice
i+=1
# iteramos mientras que el valor de L[j] sea mayor que pivote
while L[j] > pivote:
# decrementamos el índice
j-=1
# si i es menor o igual que j significa que los índices se han cruzado
if i < = j:
# creamos una variable temporal para guardar el valor de L[j]
x = L[j]
# intercambiamos los valores de L[j] y L[i]
L[j] = L[i]
L[i] = x
# incrementamos y decrementamos i y j respectivamente
i+=1
j-=1
# si first es menor que j mantenemos la recursividad
if first < j:
L = quicksort(L, first, j)
# si last es mayor que i mantenemos la recursividad
if last > i:
L = quicksort(L, i, last)
# devolvemos la lista ordenada
return L
Para evitar que QuickSort se ejecute con un tiempo de ejecución de O(n2) en ciertas permutaciones algunas implementaciones usan otros algoritmos para ordenar las secuencias pequeñas de particiones o también cuando se da el caso de que el número de recursiones sea superior al esperado.