El algoritmo QuickSort utiliza la técnica de divide y vencerás para estructurar sus elementos de una forma efectiva haciendo el uso de llamadas recursivas. Con tomar uno de sus elementos, empieza a mover los demás elementos dependiendo de si son menor o mayor que el elemento elegido.
Los algoritmos de ordenamiento son de gran uso en muchas aplicaciones en la vida real para la reestructuración de elementos en un arreglo y operar sobre ellos de distintas formas: búsqueda de ciertos valores, elemento mayor o menor, el valor medio, entre otros.
La idea principal de QuickSort es elegir un valor llamado “pivote” y trabajar con los demás elementos con respecto al pivote. Hay tres opciones para elegir este valor:
-
Elegir el primer valor del arreglo.
-
Elegir el último valor del arreglo.
-
Elegir el valor del medio del arreglo.
-
Elegir un elemento al azar.
Ahora, se pasa a hacer un tipo de partición del arreglo. La idea es posicionar el pivote en la posición correcta. ¿Cómo se hace esto? Los valores menores al pivote se quedan a la izquierda del mismo y los valores mayores a su derecha. Luego de esto, se pasa a ordenar de la misma forma los arreglos partidos haciendo llamadas recursivas.
Código de QuickSort implementado en C++
void quickSort(int arr[], int low, int high) { if (low < high){ // pi es el index de partición. “partition” coloca el pivote donde corresponde. int pi = partition(arr, low, high); // Llamadas recursivas para volver a hacer quicksort en ambas particiones. quickSort(arr, low, pi - 1); // Del índice inicial hasta antes de pivote. quickSort(arr, pi + 1, high); // Del valor delante del pivote hasta el final. } } int partition (int arr[], int low, int high) { // low: indice inicial, high: indice final int pivot = arr[high]; // pivote int i = (low - 1); // índice del elemento más a la derecha. for (int j = low; j <= high - 1; j++) { // Para j = low; j menor o igual a antes de pivote. // Si el elemento actual es menor al pivote. if (arr[j] < pivot){ i++; // incrementa el índice de más a la derecha. swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } |
Entiéndase por “swap” como una función que intercambia de lugar los valores de un arreglo. Luego de hacer las particiones necesarias y ordenarlas una por una, el arreglo queda completamente ordenado.
QuickSort es uno de los algoritmos más utilizados por su eficiencia, pero esta va dependiendo de lo que se elija como pivote. La mejor opción sería seleccionar el elemento del medio, ya que si se elige alguno de los extremos y este elemento es el mínimo o máximo, puede ocasionar una ejecución de peor caso ya que siempre se hará una partición de una lista vacía y la lista completa.
Referencias
Joyanes Aguilar, L., & Zahonero Martínez, I. (1998). Estructura de Datos algoritmos, abstracción y objetos. (1.a ed.). New York, Estados Unidos: McGraw-Hill Education.s
Fernández, G. (2019, 18 enero). Algoritmos de ordenación: Quicksort en Javascript - Gerardo Fernández. Recuperado 21 de noviembre de 2020, de https://latteandcode.medium.com/algoritmos-de-ordenaci%C3%B3n-quicksort-en-javascript-f064db39e6ad
InterviewBit. (s. f.). Quicksort Algorithm. Recuperado 21 de noviembre de 2020, de https://www.interviewbit.com/tutorial/quicksort-algorithm/