Resumen: implementar QuickSort en Java usando recursividad, selección de pivote y principio divide y vencerás para ordenar arreglos, ya sea de tipo int o de tipo String.

QuickSort en Java

Este algoritmo es uno de los más rápidos al momento de ordenar arreglos, en comparación con el ordenamiento de burbuja.

Así como es más rápido, es un poco complejo de entender, pero básicamente se trata de dos cosas:

Partición o pivote

Primero debemos encontrar la partición del arreglo, comenzamos un ciclo infinito y apuntamos dos variables al inicio y final del arreglo. Mientras cada elemento en el índice de cada variable esté en orden, acercamos las variables entre sí, es decir, aumentamos izquierda y disminuimos derecha.

Si la izquierda superó o igualó a la derecha, significa que los elementos ya estaban en orden así que regresamos el índice de la derecha para que de ahí se divida el arreglo, y termina el ciclo.

En caso de que la izquierda no haya superado a la derecha significa que por ahí había un elemento desordenado, por lo que intercambiamos las variables de cada extremo y el ciclo se sigue ejecutando.

Quicksort

La partición es lo que realmente ordena el arreglo e indica de dónde partir para dividir el arreglo. Entonces en el quicksort invocamos a particion para saber cómo dividir el arreglo (es decir, desde cuál índice) e invocamos a quicksort dos veces con cada mitad del arreglo.

Código Java para arreglo de enteros

Veamos el código que va a generar todo esto. Primero vemos el de la partición, que es el que ordena y selecciona desde dónde dividir el arreglo:

See the gist on github.

Es realmente sencillo, y al final regresamos el índice en donde se va a dividir el arreglo. Después, en la implementación, usamos recursión como lo dije:

See the gist on github.

La función recibe el arreglo, el inicio y el fin. Después utiliza esos elementos para obtener el índice para dividir, y envía las dos mitades a ordenarse.

La función no regresa nada porque ordena el arreglo internamente.

Así que al invocarla por primera vez debemos pasar el arreglo, el 0 y la longitud - 1.

Quicksort en Java para arreglos de cadena o String

Ahora veamos cómo ordenar un arreglo de cadena usando QuickSort. Esto es igualmente fácil y el código casi no cambia, pues usamos compareTo para comparar cadenas en Java.

El algoritmo es el mismo, solo cambia la comparación por lo que no explicaré el método. La selección del pivote y la función quicksort queda así (presta atención a la línea 12):

See the gist on github.

Si te molestan los comentarios puedes removerlos, al final el código es realmente poco, lo complejo es entenderlo de manera humana.

Poniendo todo junto

Ahora voy a demostrar que lo expuesto realmente funciona; veamos cómo probar los métodos. Queda así:

See the gist on github.

Estoy usando Arrays.toString para imprimir el arreglo de forma rápida; si tú quieres, puedes imprimirlos con un ciclo o algo así.

La salida de la ejecución del código es:

Si tú quieres probarlo puedes ejecutar el código en línea.

Te invito a ver el método de la burbuja en Java, el método QuickSort en C o más tutoriales sobre Java.