Quick Sort

Quick Sort es un algoritmo de ordenación rápido que utiliza la estrategia divide y vencerás.

La idea básica es:

1. Elegir un pivote (un elemento de la lista).
2. Reorganizar los demás elementos para que los menores que el pivote queden a su izquierda y los mayores a su derecha.
3. Aplicar el mismo proceso recursivamente a las sublistas de izquierda y derecha hasta que toda la lista esté ordenada.

Paso a paso con un ejemplo

Supongamos que queremos ordenar esta lista de menor a mayor:

[8, 3, 1, 7, 0, 10, 2]

Paso 1: Elegir un pivote Elegimos, por ejemplo, el primer elemento: 8.

Paso 2: Reorganizar según el pivote Movemos todos los números menores que 8 a la izquierda y los mayores a la derecha:

[3, 1, 7, 0, 2, 8, 10]

Ahora 8 está en su posición correcta.

Paso 3: Aplicar Quick Sort a las sublistas

• Sublista izquierda: [3, 1, 7, 0, 2]
• Sublista derecha: [10] (ya está ordenada, solo tiene un elemento)

Ordenando la sublista izquierda [3, 1, 7, 0, 2]

Elegimos pivote 3. Colocamos menores a la izquierda y mayores a la derecha:

[1, 0, 2, 3, 7]

• 3 ya está en su posición correcta.
• Sublista izquierda: [1, 0, 2]
• Sublista derecha: [7] (ya ordenada)

Ordenando [1, 0, 2]

Pivote 1. Reorganizamos:

[0, 1, 2]

• 1 queda en su lugar.
• Sublistas [0] y [2] ya están ordenadas.

Paso 4: Juntando todas las sublistas

[0, 1, 2, 3, 7, 8, 10]

Todos los elementos están ordenados.

Resumen visual del proceso

[8, 3, 1, 7, 0, 10, 2]
pivote 8 → [3,1,7,0,2] 8 [10]
pivote 3 → [1,0,2] 3 [7]
pivote 1 → [0] 1 [2]
Resultado final: [0,1,2,3,7,8,10]