Quicksort es uno algoritmos de ordenación más utilizados en las librerías bases de los lenguajes de programación, por su eficiencia y por su sencillez. Probablemente ya has escuchado o incluso conozcas este algoritmo, sin embargo siempre es bueno repasar lo básico porque, por ejemplo, si estas buscando empleo, es muy probable
que en una entrevista de trabajo, especialmente empresas de EEUU, te pidan implementar Quicksort o te pregunten sobre alguno de los algoritmos básicos de
ordenación o estructuras de datos como los Heaps.
Un poco de historia
Este algoritmo fue
inventado por Tony Hoare a finales de los 60s y también es la base
de otros como Quickselect -creado por el mismo Hoare- sin duda, es muy
interesante y es uno de los métodos de ordenación “Linearítmicos”
más eficientes que existen, sin embargo no siempre garantiza O(nlogn)
en su peor caso la complejidad de este algoritmo es cuadrática, eso
va a depender de la calidad de pivote que se elija. Ha sido muy estudiado, especialmente por Robert Sedgewick y utiliza la técnica de Divide and Conquer.
Descripción del algoritmo
Obviamente esta es una explicación mundana, como
mencioné anteriormente el algoritmo se ha estudiado ampliamente, incluyendo pruebas
matemáticas rigurosas. Sin embargo mi intención es que se pueda
entender de manera fácil. Para una explicación más completa ver la referencia del libro de Sedgewick al final del post o buscar en Wikipedia. Anteriormente escribí sobre el Heapsort que garantizaba O(nlogn) Quicksort es diferente porque la eficiencia del algoritmo va a depender del elemento pivote.
Los pasos son los siguientes:
1- Seleccionar un
elemento pivote en el array para dividirlo en 2 partes (este
procedimiento generalmente se denomina partition ya que “parte”
el array en dos).
2- Mover todos los
elementos menores al pivote al lado izquierdo.
3- Mover todos los
elementos mayores al pivote al lado derecho.
4- Repetir
recursivamente en el pedazo izquierdo y usando como división el pivot.
Como vemos es relativamente sencillo de entender, en cuanto al elemento pivote, hay muchos métodos
que se han desarrollado para elegir un pivote adecuado, el
recomendado por Sedgewick (y uno de los más usados) es el “Median
of Three” que básicamente es elegir la mediana entre 3 números (primer, medio y último elemento del array o del pedazo según su índice).
Ejemplo: si tenemos un array [8 1 4 3 7 5 6] elegimos 8 3 6 y el median of three sería (Med = 6).
Nota: La función
partition retorna el índice del pivote y posiciona los elementos menores a su izquierda y los mayores a su derecha (No necesariamente el índice retornado es el índice inicial del pivote) una vez finalizado el algoritmo de partition el elemento en
ese indice ya se encuentra ordenado.
Ejemplo: supongamos que tenemos el siguiente array: [90 70 10 60 50 30 20 40 80 0] y queremos ordenarlo de forma creciente usando Quicksort:
Lo primero sería seleccionar el pivote, para efectos prácticos vamos a elegir siempre el elemento en la mitad, en este caso el 50
Pivot: 50, Índice del pivot: 4
El segundo y tercer paso, es mover los elementos menores al lado izquierdo y los mayores al lado derecho, si hacemos esto el array quedaría de la siguiente forma:
Pivot: 50, Índice del pivot: 5
[0 40 10 20 30 50 60 70 80 90]
Vemos como los elementos menores a 50 están a la izquierda, y los mayores a la derecha. Nótese como el índice del pivot cambia, a partir de ahora el número 50 está ordenado y no va a cambiar su posición.
El siguiente paso es dividir el array en dos pedazos, a partir del índice del pivot, en este caso sería,
Pedazo 1: [0 40 10 20 30]
Pedazo 2: [60 70 80 90]
Después repetimos los pasos recursivamente en cada "pedazo" y el caso base (que termina la recursividad) sería que la longuitud del pedazo sea <= 1 porque no tiene sentido ordenar un arreglo de 1 elemento.
Implementación de Quicksort en Golang
Ejemplo: supongamos que tenemos el siguiente array: [90 70 10 60 50 30 20 40 80 0] y queremos ordenarlo de forma creciente usando Quicksort:
Lo primero sería seleccionar el pivote, para efectos prácticos vamos a elegir siempre el elemento en la mitad, en este caso el 50
Pivot: 50, Índice del pivot: 4
[90 70 10 60 50 30 20 40 80 0]
El segundo y tercer paso, es mover los elementos menores al lado izquierdo y los mayores al lado derecho, si hacemos esto el array quedaría de la siguiente forma:
Pivot: 50, Índice del pivot: 5
[0 40 10 20 30 50 60 70 80 90]
Vemos como los elementos menores a 50 están a la izquierda, y los mayores a la derecha. Nótese como el índice del pivot cambia, a partir de ahora el número 50 está ordenado y no va a cambiar su posición.
El siguiente paso es dividir el array en dos pedazos, a partir del índice del pivot, en este caso sería,
Pedazo 1: [0 40 10 20 30]
Pedazo 2: [60 70 80 90]
Después repetimos los pasos recursivamente en cada "pedazo" y el caso base (que termina la recursividad) sería que la longuitud del pedazo sea <= 1 porque no tiene sentido ordenar un arreglo de 1 elemento.
Implementación de Quicksort en Golang
<EOF>
Arriba una
implementación en Golang, como me gusta Go!, donde se puede ver la implementación del
algoritmo explicado en el post, la función más interesante del código es partition ya que se va a encargar de seleccionar el pivote y situar
los elementos menores al pivote a su izquierda y los mayores a su
derecha, al final retorna el índice del pivote. En cuanto a la selección del pivote; en el código simplemente se elige el elemento del medio, aunque sólo hay que modificar la función getPivot para implementar el "Median of Three" o cualquier otro método.
Referencias
Implementación de Quicksort en C#: Mi repositorio de Github
No hay comentarios:
Publicar un comentario