Algoritmos de ordenación

Python ya ofrece la función sorted() y el método .sort() para ordenar una lista sin escribir ni una línea de lógica de ordenación. Pero entender cómo ordenan realmente esas herramientas es un ejercicio clásico de pensamiento algorítmico: obliga a razonar sobre comparaciones, intercambios y recorridos de una lista, y sienta las bases para entender la eficiencia de un algoritmo (algo que se retomará más adelante en el curso).

A continuación se explican cinco de los algoritmos de ordenación clásicos más conocidos.

Bubble Sort

Bubble Sort (ordenamiento de burbuja) es un algoritmo muy simple que funciona comparando elementos adyacentes y cambiándolos de posición si están en el orden incorrecto.

• Repite este proceso varias veces hasta que toda la lista esté ordenada.
• Se llama "burbuja" porque los valores más grandes "suben" poco a poco hacia el final de la lista, como burbujas en el agua.

Bubble Sort es fácil de entender, pero no es eficiente para listas grandes, porque compara muchos elementos varias veces.

Paso a paso con un ejemplo

Lista inicial

[5, 2, 9, 1, 5]

Primera pasada (comparar y mover burbujas)

1. Comparar 5 y 2 → 5 > 2 → intercambiamos → [2, 5, 9, 1, 5]
2. Comparar 5 y 9 → 5 < 9 → no cambiamos → [2, 5, 9, 1, 5]
3. Comparar 9 y 1 → 9 > 1 → intercambiamos → [2, 5, 1, 9, 5]
4. Comparar 9 y 5 → 9 > 5 → intercambiamos → [2, 5, 1, 5, 9]

El número más grande 9 ya está en su posición final.

Segunda pasada

1. Comparar 2 y 5 → no cambiamos → [2, 5, 1, 5, 9]
2. Comparar 5 y 1 → 5 > 1 → intercambiamos → [2, 1, 5, 5, 9]
3. Comparar 5 y 5 → no cambiamos → [2, 1, 5, 5, 9]

Ahora el segundo número más grande 5 ya está en su lugar.

Tercera pasada

1. Comparar 2 y 1 → 2 > 1 → intercambiamos → [1, 2, 5, 5, 9]
2. Comparar 2 y 5 → no cambiamos → [1, 2, 5, 5, 9]

Cuarta pasada

No hay cambios → la lista ya está ordenada:

[1, 2, 5, 5, 9]

Resumen visual del proceso

[5, 2, 9, 1, 5]
→ [2, 5, 9, 1, 5]
→ [2, 5, 1, 9, 5]
→ [2, 5, 1, 5, 9]  # 9 en su lugar
→ [2, 1, 5, 5, 9]  # 5 en su lugar
→ [1, 2, 5, 5, 9]  # lista ordenada

Insertion Sort

Insertion Sort (ordenamiento por inserción) es un algoritmo que construye la lista ordenada de izquierda a derecha, insertando cada elemento en su posición correcta dentro de la parte ya ordenada.

Imagina que estás ordenando cartas en tu mano: tomas una carta a la vez y la colocas en el lugar correcto.

Insertion Sort es muy eficiente para listas pequeñas o casi ordenadas, y es fácil de implementar a mano.

Paso a paso con un ejemplo

Lista inicial

[8, 3, 5, 1, 4]

Paso 1: Considerar el primer elemento como ordenado

• [8] → ya está ordenado
• Lista completa: [8, 3, 5, 1, 4]

Paso 2: Insertar el segundo elemento 3

• Comparar 3 con 8 → 3 < 8 → mover 8 a la derecha
• Insertar 3 en la posición correcta → [3, 8, 5, 1, 4]

Paso 3: Insertar el tercer elemento 5

• Comparar 5 con 8 → 5 < 8 → mover 8
• Comparar 5 con 3 → 5 > 3 → insertar 5 → [3, 5, 8, 1, 4]

Paso 4: Insertar el cuarto elemento 1

• Comparar 1 con 8 → mover 8
• Comparar 1 con 5 → mover 5
• Comparar 1 con 3 → mover 3
• Insertar 1 → [1, 3, 5, 8, 4]

Paso 5: Insertar el quinto elemento 4

• Comparar 4 con 8 → mover 8
• Comparar 4 con 5 → mover 5
• Comparar 4 con 3 → 4 > 3 → insertar 4 → [1, 3, 4, 5, 8]

Resultado final

[1, 3, 4, 5, 8]

Resumen visual

[8, 3, 5, 1, 4]  # inicial
[3, 8, 5, 1, 4]  # insertar 3
[3, 5, 8, 1, 4]  # insertar 5
[1, 3, 5, 8, 4]  # insertar 1
[1, 3, 4, 5, 8]  # insertar 4

Selection Sort

Selection Sort (ordenamiento por selección) es un algoritmo simple de ordenación que funciona seleccionando el elemento más pequeño (o más grande, según el orden deseado) de la lista y colocándolo en su posición correcta, uno a uno, hasta ordenar toda la lista.

• No necesita listas adicionales; se hace in-place.
• Se basa en encontrar repetidamente el mínimo de la parte no ordenada y colocarlo en el siguiente lugar disponible de la parte ordenada.

Algoritmo

1. Considerar la lista completa como no ordenada.
2. Buscar el elemento mínimo dentro de la lista no ordenada.
3. Intercambiar ese mínimo con el primer elemento de la lista no ordenada.
   • Ahora la primera posición está ordenada.
4. Repetir el proceso para el resto de la lista (excluyendo las posiciones ya ordenadas):
   • Buscar el mínimo en la sublista restante.
   • Colocarlo en la siguiente posición correcta.
5. Continuar hasta que todas las posiciones estén ordenadas.

Cómo se organiza la lista internamente

• La lista se divide mentalmente en dos partes:
  1. La sublista ordenada al inicio.
  2. La sublista no ordenada al final.
• En cada iteración, el tamaño de la sublista ordenada aumenta en uno, y la sublista no ordenada disminuye en uno.
• Después de tantas iteraciones como elementos tenga la lista, toda la lista estará ordenada.

Características clave

• Siempre hace n-1 iteraciones si la lista tiene n elementos.
• Es un algoritmo determinista y estable si se implementa cuidadosamente.
• Fácil de entender y de implementar, pero no es eficiente para listas grandes, porque siempre busca el mínimo de manera completa en cada paso.

Paso a paso con un ejemplo

Lista inicial

[8, 3, 5, 1, 4]

Paso 1: Buscar el mínimo en toda la lista [8, 3, 5, 1, 4]

• Mínimo = 1 → intercambiar con el primer elemento 8
• Lista ahora: [1, 3, 5, 8, 4]

Paso 2: Buscar el mínimo en la sublista [3, 5, 8, 4]

• Mínimo = 3 → ya está en la posición correcta
• Lista ahora: [1, 3, 5, 8, 4]

Paso 3: Buscar el mínimo en [5, 8, 4]

• Mínimo = 4 → intercambiar con el primer elemento de la sublista 5
• Lista ahora: [1, 3, 4, 8, 5]

Paso 4: Buscar el mínimo en [8, 5]

• Mínimo = 5 → intercambiar con 8
• Lista ahora: [1, 3, 4, 5, 8]

Paso 5: Solo queda [8] → ya está ordenado

Resultado final

[1, 3, 4, 5, 8]

Merge Sort

Merge Sort es otro algoritmo de ordenación basado en la estrategia divide y vencerás. Merge Sort siempre divide primero y combina después, a diferencia de Quick Sort que elige un pivote y organiza alrededor de él.

La idea básica es:

1. Dividir la lista en mitades hasta que cada sublista tenga un solo elemento (o esté vacía).
2. Combinar (merge) esas sublistas de manera que queden ordenadas.
3. Repetir el proceso hasta reconstruir la lista completa, ya ordenada.

Paso a paso con un ejemplo

Supongamos que queremos ordenar esta lista:

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

Paso 1: Dividir la lista

Dividimos la lista en dos mitades:

Izquierda: [8, 3, 1]
Derecha: [7, 0, 10, 2]

Paso 2: Dividir de nuevo hasta sublistas de un elemento

• Izquierda [8, 3, 1] → [8] y [3, 1] → [3] y [1]
• Derecha [7, 0, 10, 2] → [7, 0] y [10, 2] → [7] y [0], [10] y [2]

Ahora cada sublista tiene un solo elemento, que por definición ya está ordenada.

Paso 3: Combinar sublistas ordenadas

Combinar [3] y [1]:

[1, 3]

Combinar [8] y [1, 3]:

[1, 3, 8]

Combinar sublistas de la derecha:

• [7] y [0] → [0, 7]
• [10] y [2] → [2, 10]
• Combinar [0, 7] y [2, 10] → [0, 2, 7, 10]

Paso 4: Combinar las mitades finales

Combinar [1, 3, 8] y [0, 2, 7, 10]:

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

Ahora la lista completa está ordenada.

Resumen visual del proceso

[8, 3, 1, 7, 0, 10, 2]
→ [8, 3, 1] y [7, 0, 10, 2]
→ [8], [3,1] y [7,0], [10,2]
→ [8], [3],[1] y [7],[0],[10],[2]
→ Combinar: [1,3], [8] → [1,3,8]
→ Combinar: [0,7], [2,10] → [0,2,7,10]
→ Combinar finales → [0,1,2,3,7,8,10]

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]