Algoritmia: Quicksort

Tweet

El algoritmo Quicksort es un algoritmo de ordenación muy conocido que se caracteriza por su rápidez. Es un algoritmo recursivo encuadrado dentro de las técnicas de "divide y vencerás". Aunque hoy en día, la mayoría de lenguajes ya proporcionan en sus librerías funciones de ordenación, es necesario saber como funcionan este tipo de algoritmos ya que nunca se sabe cuando nos pueden hacer falta.

El funcionamiento del algoritmo consiste en ordenar los elementos de una lista en base a un elemento llamado pivote. En cada llamada a la función se elige un pivote y se ordenan los elementos de manera que a un lado queden todos los elemento menores que el pivote, y al otro lado queden los mayores. Se aplica el mismo proceso recursivamente a cada una de las sublistas generadas a cada lado del pivote. Los pasos a seguir son:

• Se elige un elemento de la lista que nos sirva como pivote.
• Se ordenan los elementos intercambiando los elementos de la lista de manera que nos queden 2 sublistas; una con los elementos menores que el pivote y otra con los elementos mayores.
• Una vez generadas las 2 sublistas se aplica el mismo proceso recursivamente hasta que no queden más elementos que ordenar.

Una descripción en pseucódigo sería la siguiente:

Ordenar(Lista, left, right){
               pivote = Lista[(left+right)/2]
               Mientras que (left < right){
               Mientras que (Lista[left] < pivote) entonces left = left +1
               Mientras que (Lista[right] > pivote) entonces right = right -1
               Si (left <= j) entonces 
                        intercambiamos Lista[left] con Lista[right]
                        left = left +1
                        right = right - 1
               devolver left
}


Quicksort(Lista, left, right){
              limite = Ordenar(Lista,left,right)
              Si (left < limite - 1) entonces Quicksort(Lista,left,limite-1)
             Si (limite < right) entonces Quicksort(Lista,limite,right)
}

En el ejemplo anterior el pivote simplemente se escoge como el elemento central de la lista de elementos aunque hay técnicas más efectivas para la elección del pivote.

La complejidad del algoritmo es de O(nlogn) en el caso medio y en el peor de los casos es de O(n²) y depende de la elección del pivote. Las técnicas de elección del pivote la veremos con detalle en un futuro post.