Capítulo 13. Métodos de ordenamiento: QuickSort (Parte I)

QuickSort

Pondremos nuestra atención en el funcionamiento de un nuevo método de ordenamiento que también utiliza la técnica de DyC, el QuickSort.

La idea principal del mismo consiste en elegir un elemento al azar, denominado pivot y, a partir de ese elemento, dividir la cadena en dos partes:

• A la izquierda del pivot todos los elementos menores
• A la derecha del pivot todos los elementos mayores.

Al hacer esto, el pivot queda ubicado en su posición definitiva dentro de la cadena, es decir, queda ordenado. Luego se aplica en forma recursiva el método a las dos partes restantes.

Existen distintas técnicas para la elección del pivot. Cabe destacar que una buena selección del elemento pivot significará una solución más eficiente. Cuanto más cercano al elemento mediano se encuentre el pivot, más parejas serán las dos partes de la cadena y mejor la solución. Por el contrario, cuanto más cercano a alguno de los extremos se encuentre el pivot, las partes serán más desparejas y la solución menos eficiente.

Al igual que con MergeSort veremos un ejemplo ilustrado que nos ayude a comprender la forma en que trabaja el método. Supondremos a continuación que nuestro algoritmo siempre selecciona como pivot el primer elemento de la cadena.

Señalamos a continuación el elemento pivot en negrita en las sucesivas llamadas recursivas.

Se puede observar que, a medida que el pivot es elegido, va quedando en la posición que le corresponde en la cadena ordenada. Verificar por ejemplo que el primer pivot, el número "15", queda sexto cuando es elegido y en la última cadena (la ordenada) también ocupa esa posición.

 

En el próximo capítulo presentaremos el pseudocódigo para el método de QuickSort así como también el análisis de complejidad temporal.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.