Ordenar arreglo con Quicksort en C: en este post voy a mostrarte cómo implementar el algoritmo de ordenamiento rápido o quicksort en ANSI C.

Este algoritmo destaca porque es uno de los más rápidos al momento de ordenar arreglos, además de que el mismo no ocupa arreglos temporales, simplemente intercambia variables y utiliza el método de divide y vencerás.

Al final podremos ordenar arreglos usando el algoritmo Quicksort en C.

Implementación de Quicksort en C

Para implementar este algoritmo vamos a usar el esquema de partición Hoare; el pivote siempre será el mismo (el primer elemento de la lista) y colocaremos los punteros en los extremos del arreglo.

Con “puntero” me refiero a índice del arreglo

Explicación básica de Quicksort

Nota: si quieres ir directo al código pasa al siguiente apartado.

Este algoritmo selecciona un pivote, y después establece dos apuntadores en los extremos del arreglo. Va acercando entre sí los índices (es decir, disminuye el de la derecha y aumenta el de la izquierda) hasta que encuentra un elemento que se puede intercambiar.

Un elemento intercambiable es aquel que es más pequeño que el pivote pero está a su derecha, o que es más grande que el pivote pero está a su izquierda. En otras palabras, un elemento que no está ordenado.

Si encuentra el elemento intercambiable, lo intercambia y sigue acercando los punteros hasta que los mismos se cruzan o izquierda es mayor o igual que derecha.

En caso de que los índices se crucen, se devuelve el índice de la derecha y ese se toma para dividir el arreglo y ahora aplicar lo mismo a las dos mitades, aplicando la recursión o recursividad hasta que finalmente todo el arreglo se ordenará.

Es decir, en otras palabras el algoritmo utiliza la técnica de divide y vencerás. Por cierto, la recursividad se cumple mientras izquierda sea menor que derecha.

Quicksort en C

Ahora sí a lo que venimos. Para implementar este algoritmo debemos tener una función que intercambie valores. No es estrictamente necesaria pero nos ahorra tres líneas de código además de que si la usamos aumenta la legibilidad.

Por lo tanto usaré una función que ya había explicado antes, que intercambia valores por referencia:

See the gist on github.

Después tenemos la función quicksort que recibe el arreglo y los índices inicio y fin, o izquierda y derecha. En este caso se usará recursividad así que se divide el arreglo y se invoca a quicksort 2 veces, así:

See the gist on github.

Si te fijas el algoritmo irá dividiendo el arreglo, pero usará el índice que devuelva el método particion; este método es el que realmente ordena el arreglo e intercambia valores. Queda así:

See the gist on github.

Eso es todo lo que necesitamos para usar este método de ordenamiento en C. A continuación veremos su uso.

Uso de quicksort en C

Vamos a ver un ejemplo, definimos en el método main un arreglo; también lo imprimimos para ver cómo es que se ve antes y cómo se ve después de ordenarlo usando quicksort.

See the gist on github.

El arreglo puede ser de cualquier tamaño y tener elementos de cualquier tipo. Al ejecutar el código aparece lo de la imagen del inicio del post:

Si quieres probar por ti, puedes ejecutar este algoritmo en línea.

Te invito a ver más sobre C o algoritmos en mi blog.