Algoritmo Quicksort

Unidad 2. Actividad 5

Elabora un ejemplo de un problema donde emplees cualquiera de los métodos de ordenamiento estudiados en esta unidad para su solución. Elabora el algoritmo correspondiente en un documento de Word.

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9]

[pic 10]

Elegimos un pivote: En este caso utilizare el número 4.

[pic 11]

[pic 12]

[pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19]

[pic 20]

[pic 21]

[pic 22]

[pic 23]

Menores        Mayores

            Pivote

Entonces hacemos uso de los punteros iniciando por el lado mayor diciendo que:

-10 > 4 = Se cumple y seguimos.

-7 > 4 = Si cumple.

-8 > 4 = Si cumple.

-3 > 4 = No cumple, por lo tanto movemos el 3 al puntero menor y seguimos con el mismo procedimiento, solo a que ahora a la inversa.

-9 < 4 = No cumple por lo que cambiamos el 9 de puntero y continuamos.

-5 > 4 = Si cumple.

-2 > 4 = No cumple así que cambiamos el 2 al puntero menor.

-6 < 4 = No cumple y cambiamos el 6 de puntero.

HASTA ESTE PASO TODO QUEDA DE LA SIGUIENTE MANERA.

[pic 24]

[pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32]

[pic 33][pic 34]

Hasta este punto los 2 punteros quedan juntos por lo que ahí ponemos el pivote y  a partir de ahí separamos la lista como se muestra a continuación:

[pic 35][pic 36][pic 37]

        LISTA 2

[pic 38][pic 39][pic 40][pic 41][pic 42][pic 43]

LISTA 1

-Ahora volvemos a iniciar el proceso en cada una de las listas hasta que queden ordenadas. Iniciare por la lista 2.

[pic 44][pic 45][pic 46][pic 47][pic 48]

[pic 49][pic 50]

[pic 51][pic 52]

-10 > 6 = Si cumple.

-7 > 6 = Si cumple.

- 8 > 6 =Si cumple.

- 9 > 6 =Si cumple.

- 5 > 6 = No cumple y cambiamos de puntero.

[pic 53][pic 54][pic 55][pic 56][pic 57]

[pic 58][pic 59]

[pic 60][pic 61]

-Movemos el puntero menor y nuevamente se juntan ambos punteros por lo que ahí ponemos el pivote quedando de la siguiente manera:

[pic 62][pic 63][pic 64][pic 65][pic 66][pic 67]

[pic 68]

[pic 69]

-Nuevamente quedan otras dos listas.

[pic 70][pic 71]

        LISTA 4[pic 72][pic 73][pic 74][pic 75]

LISTA 3

-Repetimos los mismos pasos para ordenar la lista 1:

[pic 76][pic 77][pic 78]

...