En el post de hoy vamos a ver cómo ordenar un arreglo de C# (c sharp .NET) usando el algoritmo de Quicksort.

Vamos a hacer el algoritmo a mano, es decir, creando nuestras propias funciones para el ordenamiento de un array usando Quicksort o qs.

El algoritmo

Para ordenar un arreglo usando quicksort aplicamos el método de divide y vencerás. Tendremos dos apuntadores al arreglo, uno a la izquierda y uno a la derecha (o uno al inicio y otro al final).

El lugar en donde el algoritmo se divide es en el método de la partición. Este método debe indicar en qué índice del arreglo debemos hacer la división, es decir, en cuál índice separar el arreglo en 2.

Dentro del algoritmo de la partición vamos acercando los extremos mientras que cada elemento del arreglo esté ordenado. Si encontramos que hay un elemento que no está ordenado entonces intercambiamos los valores de los dos extremos.

La partición se detiene y regresa cuando hemos acercado los extremos de tal modo que la izquierda es mayor o igual a la derecha. En ese punto devolvemos el índice de la derecha, mismo que será usado para hacer otras particiones.

Al final vamos a ir dividiendo el arreglo en partes más pequeñas, y ordenando a las mismas. Pero el verdadero ordenamiento viene en la partición.

Yo sé que es mucha explicación y que puede ser confusa, pero verás que en el código se entiende de mejor manera.

Quicksort en C#

Entonces debemos implementar dos funciones en C sharp. La primera va a ser quien se encargue de ir dividiendo el arreglo eligiendo la partición, invocando a la función dentro de sí misma usando recursión.

La segunda función es la de la partición, misma que se va a encargar de ordenar el arreglo y devolver el índice en donde se quedó.

Partición

Veamos la función de C# que se encarga de ordenar la porción del arreglo:

Como puedes notar, el código se explica por sí mismo apoyándose de los comentarios. Recuerda que el verdadero orden e intercambio está en la línea 27 en caso de que los elementos no hayan estado ordenados.

Función de qs

Y ahora que ya vimos la función de partición para elegir el pivote veamos la función quicksort para aplicar el algoritmo del mismo nombre en C#:

Recuerda que aquí lo que se hace es ir dividiendo el arreglo. La primera parte es desde la izquierda hasta el pivote, y la segunda es desde el pivote + 1 hasta la derecha.

Conforme esta función se vaya invocando se va a ir partiendo al arreglo en trozos más pequeños.

Poniendo todo junto

Es momento de ver el código completo con un ejemplo. El mismo queda como se ve a continuación. Presta atención al modo de uso que está dentro del método Main.

Por cierto, en este caso he utilizado un arreglo de tipo entero pero puedes usar uno de cualquier tipo, por ejemplo uno de tipo string. Solo recuerda comparar correctamente los datos, ya que en el caso de las cadenas se usa CompareTo.

La salida ya la pudiste ver junto con el encabezado. Al final el arreglo estará ordenado usando el algoritmo quicksort.

Por aquí te dejo con más posts de C#.