Cómo funciona la clasificación rápida:
1. Dividir: Elija un elemento pivote de la matriz (a menudo el último elemento).
2. Partición: Reorganice la matriz de manera que todos los elementos menores que el pivote estén a la izquierda del pivote y todos los elementos mayores que el pivote estén a la derecha. El elemento pivotante se encuentra en su posición final ordenada.
3. Recursión: Repita los dos pasos anteriores para los subarreglos izquierdo y derecho, dividiéndolos recursivamente hasta que cada subarreglo contenga solo un elemento.
Ejemplo 1:
Considere la matriz [5, 3, 8, 2, 1, 4].
a. Dividir:elija el último elemento, 1 como pivote.
b. Dividir:
- Reorganizar la matriz:[3, 2, 1, 5, 4, 8] (1 está en su posición ordenada).
do. recursivo:
- Subarreglo izquierdo:[3, 2, 1] (ya ordenado)
- Subarreglo derecho:[5, 4, 8] (aplicar recursivamente Orden rápido)
Después de aplicar Quick Sort a ambos subarreglos, el arreglo ordenado final es:[1, 2, 3, 4, 5, 8].
Ejemplo 2:
Ordenar una matriz más grande
Considere una matriz [7, 2, 9, 5, 3, 4, 1, 8, 6].
a. Dividir:elija el último elemento, 6, como pivote.
b. Dividir:
- Reorganizar la matriz:[2, 5, 3, 4, 1, 7, 9, 6] (6 está en su posición ordenada).
do. recursivo:
- Subarreglo izquierdo:[2, 5, 3, 4, 1] (aplicar recursivamente Orden rápido)
- Subarreglo derecho:[7, 9] (ya ordenado)
Después de completar las llamadas recursivas, la matriz ordenada es:[1, 2, 3, 4, 5, 6, 7, 8, 9].
Complejidad del tiempo:
- Mejor caso:O(n log n)
- Caso promedio:O(n log n)
- Peor de los casos:O(n^2) (ocurre cuando la matriz ya está ordenada o en orden inverso)
En general, el algoritmo Quick Sort ofrece una solución de clasificación eficiente con una buena complejidad de tiempo promedio de O (n log n). Su simplicidad y versatilidad lo han convertido en un algoritmo popular para clasificar tareas en varios lenguajes de programación.