Algoritmos y Estructuras de Datos

Bubble Sort (Ordenamiento de burbuja)

Dado un arreglo de n números enteros, queremos ordenarlos en orden ascendente. Bubble sort (ordenamiento de burbuja) es uno de los algoritmos más populares y fáciles de comprender para lograr esto (aunque no es rápido, por lo que en la mayoría de soluciones de producción se usan otras técnicas para ordenar una lista de números).
Video preview
Con este algoritmo, se realizan varias pasadas sobre el arreglo y se intercambian aquellos elementos vecinos que estén fuera de orden. Entonces, si , se hace un intercambio para asegurarnos de que el arreglo vaya quedando en orden ascendente.
Concretamente, tomamos el arreglo inicial a (por ejemplo, a es [4, 1, -1, 0, 2, 8]) y miramos sus dos primeros elementos. Si no están en orden, los intercambiamos (en este caso [1, 4, -1, 0, 2, 8]). Luego pasamos a la siguiente pareja. Si no están en orden, nuevamente los intercambiamos (en este caso [1, -1, 4, 0, 2, 8]). Repetimos este proceso hasta llegar al final del arreglo (en nuestro ejemplo, esto produce [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → sin cambio → listo).
Después de la primera pasada, volvemos a empezar desde el inicio del arreglo. Observamos la primera pareja y las comparamos: si no están en orden, las intercambiamos. Luego avanzamos a la siguiente pareja, y así sucesivamente hasta el final del arreglo. En nuestro ejemplo, esto da como resultado: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → sin cambio.
Este proceso se repite hasta que el arreglo queda completamente ordenado:
a = [...]
while True:                                 # se ejecuta hasta que el arreglo esté ordenado
    is_sorted = True                        # si algo cambia, esto se pone en False
    for i in range(len(a) - 1):             # recorre de 0 ... n-2
        if a[i] > a[i + 1]:                 # si algo está fuera de orden
            is_sorted = False               # => el arreglo no estaba ordenado
            a[i], a[i + 1] = a[i + 1], a[i] # intercambia a[i] y a[i + 1]
    
    if is_sorted:                           # detiene el proceso si a está ordenado
        break
print(a)
Podemos realizar una optimización para ahorrar algunos pasos innecesarios:
  • Después de cada iteración, los elementos más grandes se van colocando al final del arreglo. Por lo tanto, tras k pasadas, los últimos k elementos del arreglo ya están ordenados. Así, podemos omitir revisar esas posiciones en el ciclo interno.
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = límite superior para el ciclo interno
    is_sorted = True                        # si algo cambia, esto se pone en False
    for i in range(u):                      # recorre de 0 ... u-1
        if a[i] > a[i + 1]:                 # si algo está fuera de orden
            is_sorted = False               # => el arreglo no estaba ordenado
            a[i], a[i + 1] = a[i + 1], a[i] # intercambia a[i] y a[i + 1]
    
    if is_sorted:                           # detiene el proceso si a está ordenado
        break
print(a)
El peor caso para este algoritmo ocurre cuando los números están en orden completamente inverso (descendente) en lugar de ascendente. En ese escenario, Bubble sort realiza operaciones. Se trata de un número elevado en comparación con otros algoritmos más rápidos que veremos más adelante en el curso.
Simulemos el algoritmo con algunos ejemplos:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ do nothing
Extracurricular (interesting video)
Hay un excelente video en YouTube creado por Lines That Connect que profundiza más en el algoritmo de Bubble Sort y explica de manera muy visual la curva que se forma al ejecutarlo.
Video preview
Video de Lines That Connect - La curva de Bubble Sort.

Challenge

n personas participan en una competencia. Se te pide ordenarlas en orden ascendente según su estatura. En cada paso, se te permite pedir a dos participantes vecinos que intercambien sus lugares. No tienes mucho tiempo, así que quieres hacerlo de la manera más eficiente posible.
Has decidido escribir un programa que imprima los índices de los participantes que deben cambiar de posición. La indexación empieza en 0.

Entrada

La primera línea de la entrada contiene un solo entero n (1 ≤ n ≤ 1000).
La siguiente línea contiene n números enteros separados por espacio ( ≤ ≤ ) que representan las estaturas de los participantes.

Salida

El programa debe imprimir las parejas de índices de los participantes que necesitan intercambiar posiciones. Cada pareja se imprime en una línea independiente. Si hay múltiples respuestas óptimas, cualquiera de ellas es válida.

Ejemplos

Input
Output
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Explicación

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue