(void *) blog

Posted on by fortytwo_de


¿Qué no se puede resolver con Quicksort?

Como otros algoritmos de sorting de listas, su misión es ordenar una lista de números según un criterio dado en el menor número de tiempo. Existen multitud de algoritmos, pero Quicksort es el más sencillo de implementar en C: viene incluido en la librería estándar. Concretamente, en <string.h>.

Algoritmo
  • Elegir un elemento cualquiera de la lista, llamado pivot.
  • Mover el elemento hasta que todos los valores que queden a la izquierda de pivot tengan menor valor, y todos los elementos a la derecha de pivot tengan mayor valor.
  • Reordenar la sub-lista que queda a la izquerda, recursivamente, hasta que esté ordenada.
  • Reordenar la sub-lista de la derecha, recursivamente, hasta que esté ordenada.

Por supuesto, esta es la definición "teórica". Se pueden hacer multitud de optimizaciones, pero para explicar el algoritmo sirve.

Ejemplo

Tenemos la lista 7 8 3 9 1 3 4 0. El resultado final será 0 1 3 3 4 7 8 9. Para ordenarla, elegiremos un valor pivot. En este caso, arbitrariamente, elijo 9. El algoritmo Quicksort hace lo siguiente:

Marco el pivot con [X], para mayor claridad.

7 8 3 [9] 1 3 4 0
7 8 3 1 [9] 3 4 0
7 8 3 1 3 [9] 4 0
7 8 3 1 3 4 [9] 0
7 8 3 1 3 4 0 [9]

Se sigue con el algoritmo ordenando la lista que queda a la izquierda, es decir, los que tienen menor valor.

7 8 3 1 [3] 4 0 9
7 8 3 [3] 1 4 0 9
7 8 [3] 3 1 4 0 9
7 [3] 8 3 1 4 0 9
[3] 7 8 3 1 4 0 9

Esta es la única forma de colocar a 3 de tal forma que todos los elementos de la izquierda tengan menor valor.

3 7 8 3 [1] 4 0 9
3 7 8 [1] 3 4 0 9
3 7 [1] 8 3 4 0 9
3 [1] 7 8 3 4 0 9
[1] 3 7 8 3 4 0 9
1 3 [7] 8 3 4 0 9
1 3 8 [7] 3 4 0 9
1 3 8 3 [7] 4 0 9
1 3 8 3 4 [7] 0 9
1 3 8 3 4 0 [7] 9
1 3 8 3 4 [0] 7 9
1 3 8 3 [0] 4 7 9
1 3 8 [0] 3 4 7 9
1 3 [0] 8 3 4 7 9
1 [0] 3 8 3 4 7 9
[0] 1 3 8 3 4 7 9
0 1 3 8 [3] 4 7 9
0 1 3 [3] 8 4 7 9
0 1 3 3 [8] 4 7 9
0 1 3 3 4 [8] 7 9
0 1 3 3 4 7 [8] 9

Y la lista está ordenada.

Nota: realmente, el ejemplo no es del todo correcto, ya que no expreso la recursión de una forma comprensible. Pero se entiende, en general.

Posted on by fortytwo_de | Posted in Algoritmos, C, Programación


One Response to Quicksort

  1. Basajaun says:


    La leche yo esto lo día cuando aprendía a programar, de donde te sacas todo eso? xDD btw muy bien explicado ;)


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>