Quicksort
Quicksort es un algoritmo de ordenación que se utiliza para ordenar los elementos de una matriz. Fue creado por Tony Hoare en 1959, y sigue siendo ampliamente utilizado hoy en día. Quicksort crea particiones dentro del array, lo que significa esencialmente que divide el array en dos partes, y luego continúa dividiendo esas partes en más partes, y ordenando a lo largo del camino. Hace la ordenación real por la naturaleza de ser una ordenación por comparación. Esto significa que elige un punto pivote en el array, y luego lo compara con todos los demás puntos del array.
Visualización animada del algoritmo quicksort. Las líneas horizontales son valores de pivote
Algoritmo
- Escoge cualquier elemento del array, este será ahora el punto de pivote.
- Partición de los elementos. Compara todos los elementos del array con el pivote, los que son más bajos que el pivote se mueven a la izquierda del pivote, y todos los elementos del array que son más altos que el pivote se mueven a la derecha del pivote. Observa que nuestro pivote está ahora en su posición ordenada.
- Recurrir a las dos particiones. Aplique los dos pasos anteriores a las dos particiones que creamos en el paso 2.
A menudo se elige el elemento más a la izquierda como pivote. La recursión significa que el algoritmo ejecuta el mismo algoritmo exacto en las dos particiones que fueron creadas por las comparaciones con el pivote. Obsérvese que este algoritmo seguirá partiendo el array en subarreglos, y dividiendo esos subarreglos en subarreglos aún más pequeños. Cada vez que haga esto, elegirá un nuevo pivote dentro de la submatriz y comparará los elementos con la submatriz. El caso base es cuando el algoritmo llega a una submatriz con un solo elemento, en la que simplemente se detiene porque un elemento no necesita ser ordenado.
