Algoritmos de ordenamiento III. Quick Sort


Nos vemos una vez más, inmersos en este interesante tema relacionado con los algoritmos de ordenamiento. En artículos pasados estuvimos viendo detalles relacionados a estos métodos y les mostré cómo funcionaban cada uno de los vistos, por ello si aún no has leído estos artículos, te recomiendo leas primero el artículo Algoritmos de ordenamiento I donde sentamos las bases para algoritmos avanzados de ordenamiento y luego en un segundo artículo titulado Algoritmos de ordenamiento II, vimos un tipo de ordenamiento conocido como Merge Sort (Ordenamiento por mezcla) y lo analizamos a fondo.

En el último encuentro sobre este tema, veremos uno de los métodos de ordenamiento más rápidos que existen, conocido como Quick Sort (Ordenamiento rápido).

El algoritmo Quick Sort, es uno de los algoritmos de complejidad N*N existentes, pero te preguntarás entonces, ¿Por qué es usado?, ¿Por qué no usar un burbuja?, pues te comento, que este método en el peor de los casos puede llegar a ser de complejidad cuadrática, pero si hacemos un análisis de la cantidad de iteraciones promedio que realiza para ordenar una lista de elementos, podemos asegurar que este método es de complejidad N*log(N).

A lo largo del artículo, realizaremos un análisis de su funcionamiento y una vez que hayamos entendido como funciona, pasaremos a programarlo en lenguaje C++.

¿Cómo funciona Quick Sort?

Quick Sort, al igual que el Merge Sort, utiliza la técnica Divide y Vencerás, que se basa en dividir el problema en varios sub-problemas. Pero, ¿Cómo dividir el problema?, pues para esto se utiliza la estrategia de seleccionar un pivote.

Para entender la utilización del pivote, veremos cómo funciona esto en una lista. La idea es fijar un elemento cualquiera (será nuestro pivote) en la lista, y a partir de esto recorremos con dos cursores el listado (uno desde el principio y otro desde el final).

Los cursores van a hacer el trabajo de ordenar los elementos menores que el pivote a la izquierda y los elementos mayores que el pivote a la derecha. A continuación te muestro el proceso.

Seleccionamos el pivote (Fig1).

Elección del pivote

Fig1: Elección del pivote

Fijamos los cursores (Fig2). Si el primer cursor es mayor igual que el pivote y el segundo cursor es menor, los cambiamos y movemos a la siguiente posición los cursores.

Los cursores

Fig2: Los cursores

Si los cursores ya están en orden (Fig3), los movemos a la siguiente posición.

 Iteración de los cursores

Fig3: Iteración de los cursores

Cuando la posición del primer cursor deje de ser menor que la posición del segundo (Fig4), entonces comprobamos que el cursor sea mayor que el pivote, en caso afirmativo los cambiamos, y agregamos el pivote al final.

Convergencia de los cursores

Fig4: Convergencia de los cursores

Con esto hecho, contamos con dos sub-listas, a la izquierda los menores que el pivote y la derecha los mayores iguales al pivote (Fig5).

Sublistas ordenadas

Fig5: Sublistas ordenadas

En este proceso hay que tener en cuenta otro caso, y es cuando ambos cursores son menores que el pivote, en el cual se movería solo el primer cursor, y en caso contrario, donde ambos cursores sean mayores que el pivote, entonces se movería solo el segundo.

Una vez que entendemos esta forma de sub-ordenar la lista (menores a la izquierda y mayores a la derecha), entonces pasaremos a realizar la misma acción para la sub-lista izquierda (que comprende los elementos desde el inicio de la lista hasta el primer cursor) y para la sub-lista derecha (que comprende los elementos desde el primer cursor hasta el final de la lista). Este proceso se realiza consecutivamente, mientras las sub-listas tengan más de 1 elemento, dado que, con un solo elemento se considera ordenada. Cuando se termina el proceso de ordenamiento para cada sub-lista, entonces la lista original quedará completamente ordenada.

Árbol del MergeSort

Fig6: Árbol del MergeSort

Al igual que el método Merge Sort, podemos notar que este método forma un árbol binario (Fig6), y para llevarlo a la programación, tenemos que realizarlo por medio de una función recursiva.

Quick Sort implementado en C++

/**
 * Descripción de los parámetros
 *
 * @params:
 *
 * @var inicio: Inicio del intervalo a ordenar
 * @var fin   : Fin del intervalo a ordenar
 * @var lista : La lista en la que ordenaremos el intervalo, [inicio,fin] 
 *
 **/
void QuickSort(int inicio, int fin, int *lista){
    //Si la sub-lista tiene un solo elemento no hacemos nada.
    if(fin - inicio <= 1) 
        return;          
    
    //Si la sub-lista tiene 2 elementos, los comparamos y ubicamos en la posición correcta.
    if(fin-inicio == 2){
      if(lista[inicio]>lista[inicio+1])
        swap(lista[inicio],lista[inicio+1]);
      return;
    }

    //Seleccionamos el pivote y ubicamos los cursores.
    int pivote = fin-1;
    int i=inicio,
        j=fin-2;
   
    //A esta sub-lista le hacemos el proceso de ordenamiento visto anteriormente.
    while( i < j){
         if(lista[i] >= lista[pivote] && lista[j] < lista[pivote]){             
            swap(lista[i],lista[j]);
             i++;j--;
         }else if(lista[i] >= lista[pivote] && lista[j] >= lista[pivote]){
            j--;
        }else if(lista[i] < lista[pivote] && lista[j] < lista[pivote]){
             i++;
         }else{
             i++;
             j--;
         }
     }
     //Si el primer cursor es mayor que el pivote, los cambiamos.
     if(lista[i] > lista[pivote]){
        swap(lista[i],lista[pivote]);
    }

    // Si el segundo cursor no llegó al inicio del intervalo, 
    // mandamos a ordenar la sub-lista izquierda.
    if(j > inicio){
        QuickSort(inicio, i+1, lista);
    }

    //Ordenamos la sub-lista derecha.
    QuickSort(i+1, fin, lista);
}

Conclusión del tema

Bien, esto es todo lo que veremos en cuanto a métodos de ordenamiento, pero eso no quiere decir que no existan otros, hay disímiles formas de ordenar listas de elementos, solo decidí darte algunos de los principales métodos de ordenamiento existentes, desde los más triviales como el Burbuja y el Mínimo sucesivo, hasta métodos más robustos y complejos que optimizan el ordenamiento, como el Merge Sort y el Quick Sort.

Si deseas conocer otros algoritmos de ordenamiento, te recomiendo este artículo de Wikipedia, donde aparecen muchos de estos algoritmos, con sus complejidades y pseudocódigos. No obstante, si conoces algún otro que creas importante mencionar y no se haya tratado, te invito a compartirlo en los comentarios.