1. Información general
En este tutorial, exploraremos el algoritmo QuickSort en detalle, centrándonos en su implementación de Java.
También discutiremos sus ventajas y desventajas y luego analizaremos su complejidad de tiempo.
2. Algoritmo QuickSort
Quicksort es un algoritmo de clasificación que aprovecha el principio de divide y vencerás. Tiene una complejidad media de O (n log n) y es uno de los algoritmos de clasificación más utilizados, especialmente para grandes volúmenes de datos.
Es importante recordar que Quicksort no es un algoritmo estable. Un algoritmo de clasificación estable es un algoritmo en el que los elementos con los mismos valores aparecen en el mismo orden en la salida ordenada como aparecen en la lista de entrada.
La lista de entrada se divide en dos sublistas mediante un elemento llamado pivote; una sublista con elementos menores que el pivote y otra con elementos mayores que el pivote. Este proceso se repite para cada sublista.
Finalmente, todas las sublistas ordenadas se fusionan para formar el resultado final.
2.1. Pasos del algoritmo
- Elegimos un elemento de la lista, llamado pivote. Lo usaremos para dividir la lista en dos sublistas.
- Reordenamos todos los elementos alrededor del pivote: los que tienen un valor menor se colocan antes y todos los elementos mayores que el pivote después. Después de este paso, el pivote está en su posición final. Este es el paso importante de la partición.
- Aplicamos los pasos anteriores de forma recursiva a ambas sublistas a la izquierda y a la derecha del pivote.
Como podemos ver, la ordenación rápida es naturalmente un algoritmo recursivo, como todos los enfoques de divide y vencerás.
Tomemos un ejemplo simple para comprender mejor este algoritmo.
Arr[] = {5, 9, 4, 6, 5, 3}- Supongamos que elegimos 5 como pivote para simplificar
- Primero colocaremos todos los elementos menores que 5 en la primera posición de la matriz: {3, 4, 5, 6, 5, 9}
- Luego lo repetiremos para el subarreglo izquierdo {3,4}, tomando 3 como pivote
- No hay elementos menores a 3
- Aplicamos ordenación rápida en el subarreglo a la derecha del pivote, es decir, {4}
- Esta submatriz consta de un solo elemento ordenado
- Continuamos con la parte derecha de la matriz original, {6, 5, 9} hasta que obtenemos la matriz ordenada final.
2.2. Elegir el pivote óptimo
El punto crucial en QuickSort es elegir el mejor pivote. El elemento del medio es, por supuesto, el mejor, ya que dividiría la lista en dos sublistas iguales.
Pero encontrar el elemento del medio de una lista desordenada es difícil y requiere mucho tiempo, por eso tomamos como pivote el primer elemento, el último elemento, la mediana o cualquier otro elemento aleatorio.
3. Implementación en Java
El primer método es quickSort () que toma como parámetros la matriz a ordenar, el primero y el último índice. Primero, verificamos los índices y continuamos solo si aún quedan elementos por ordenar.
Obtenemos el índice del pivote ordenado y lo usamos para llamar de forma recursiva al método partition () con los mismos parámetros que el método quickSort () , pero con índices diferentes:
public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }Continuemos con el método partition () . Para simplificar, esta función toma el último elemento como pivote. Luego, verifica cada elemento y lo intercambia antes del pivote si su valor es menor.
Al final de la partición, todos los elementos menores que el pivote están a la izquierda y todos los elementos mayores que el pivote están a la derecha. El pivote está en su posición final ordenada y la función devuelve esta posición:
private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }4. Análisis de algoritmos
4.1. Complejidad del tiempo
En el mejor de los casos, el algoritmo dividirá la lista en dos sublistas de igual tamaño. Entonces, la primera iteración de la lista completa de tamaño n necesita O (n) . Ordenar las dos sublistas restantes con n / 2 elementos requiere 2 * O (n / 2) cada una. Como resultado, el algoritmo QuickSort tiene la complejidad de O (n log n) .
En el peor de los casos, el algoritmo seleccionará solo un elemento en cada iteración, por lo que O (n) + O (n-1) +… + O (1) , que es igual a O (n2) .
En promedio, QuickSort tiene una complejidad O (n log n) , lo que lo hace adecuado para grandes volúmenes de datos.
4.2. QuickSort vs MergeSort
Analicemos en qué casos deberíamos elegir QuickSort sobre MergeSort.
Although both Quicksort and Mergesort have an average time complexity of O(n log n), Quicksort is the preferred algorithm, as it has an O(log(n)) space complexity. Mergesort, on the other hand, requires O(n) extra storage, which makes it quite expensive for arrays.
Quicksort requires to access different indices for its operations, but this access is not directly possible in linked lists, as there are no continuous blocks; therefore to access an element we have to iterate through each node from the beginning of the linked list. Also, Mergesort is implemented without extra space for LinkedLists.
In such case, overhead increases for Quicksort and Mergesort is generally preferred.
5. Conclusion
Quicksort es un elegante algoritmo de clasificación que es muy útil en la mayoría de los casos.
Generalmente es un algoritmo "en el lugar", con la complejidad de tiempo promedio de O (n log n).
Otro punto interesante para mencionar es que el método Arrays.sort () de Java usa Quicksort para ordenar matrices de primitivas. La implementación usa dos pivotes y funciona mucho mejor que nuestra solución simple, es por eso que para el código de producción generalmente es mejor usar métodos de biblioteca.
Como siempre, el código para la implementación de este algoritmo se puede encontrar en nuestro repositorio de GitHub.