Ordenamiento Burbuja | Bubble Sort

Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/5-buble_sort

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. https://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

Se trata de otro algoritmo del tipo O(n²) que, debido a su comportamiento, parecería que este es más eficiente que los anteriores (Ordenamiento por Inserción y Selección) aunque su costo depende de que tan pre-ordenada se encuentre la lista de elementos, siendo el peor de los casos un lista ordenada de manera inversa.

A pesar que se considere que este algoritmo no aporta mucho a nivel de eficiencia ni como parte de la enseñanza de las ciencias computacionales, si nos muestra una perspectiva adicional aun problema común, que fuera de lo técnico, demuestra que hay muchas soluciones y perspectivas para un mismo problema.

Ejemplo

Trataremos de ordenar la siguiente lista de enteros:

Pasos 1 → 4

  • Tomamos el primer elemento fuera de lugar y lo intercambiamos hasta encontrar una mayor.
  • Si no estamos al final de la lista, buscamos el siguiente, lo intercambiamos y repetimos hasta llegar al final de la lista.

Pasos 5 →8

  • El primer par no requiere intercambio, continuamos
  • Tomamos el siguiente y lo ubicamos detrás del próximos mayor

Pasos 9 →12

  • Intercambiamos el primer par.
  • Buscamos el siguiente fuera de lugar…

Pasos 13 →16

  • Si no realizamos intercambios, la lista está ordenada.

Implementación en Go

https://play.golang.org/p/6e4fb79rTZa

main.go.log

===========================================
ENTRADA: [100 6 34 28 97 23 61 2 7 1 44 0]
--------------- [ PASO 1 ] ---------------
100 > 6 = true
[6 100 34 28 97 23 61 2 7 1 44 0]
--------------- [ PASO 2 ] ---------------
100 > 34 = true
[6 34 100 28 97 23 61 2 7 1 44 0]
--------------- [ PASO 3 ] ---------------
100 > 28 = true
[6 34 28 100 97 23 61 2 7 1 44 0]
--------------- [ PASO 4 ] ---------------
100 > 97 = true
[6 34 28 97 100 23 61 2 7 1 44 0]
--------------- [ PASO 5 ] ---------------
100 > 23 = true
[6 34 28 97 23 100 61 2 7 1 44 0]
--------------- [ PASO 6 ] ---------------
100 > 61 = true
[6 34 28 97 23 61 100 2 7 1 44 0]
--------------- [ PASO 7 ] ---------------
100 > 2 = true
[6 34 28 97 23 61 2 100 7 1 44 0]
--------------- [ PASO 8 ] ---------------
100 > 7 = true
[6 34 28 97 23 61 2 7 100 1 44 0]
--------------- [ PASO 9 ] ---------------
100 > 1 = true
[6 34 28 97 23 61 2 7 1 100 44 0]
--------------- [ PASO 10 ] ---------------
100 > 44 = true
[6 34 28 97 23 61 2 7 1 44 100 0]
--------------- [ PASO 11 ] ---------------
100 > 0 = true
[6 34 28 97 23 61 2 7 1 44 0 100]
--------------- [ PASO 12 ] ---------------
6 > 34 = false
[6 34 28 97 23 61 2 7 1 44 0 100]
--------------- [ PASO 13 ] ---------------
34 > 28 = true
[6 28 34 97 23 61 2 7 1 44 0 100]
--------------- [ PASO 14 ] ---------------
34 > 97 = false
[6 28 34 97 23 61 2 7 1 44 0 100]
--------------- [ PASO 15 ] ---------------
97 > 23 = true
[6 28 34 23 97 61 2 7 1 44 0 100]
--------------- [ PASO 16 ] ---------------
97 > 61 = true
[6 28 34 23 61 97 2 7 1 44 0 100]
--------------- [ PASO 17 ] ---------------
97 > 2 = true
[6 28 34 23 61 2 97 7 1 44 0 100]
--------------- [ PASO 18 ] ---------------
97 > 7 = true
[6 28 34 23 61 2 7 97 1 44 0 100]
--------------- [ PASO 19 ] ---------------
97 > 1 = true
[6 28 34 23 61 2 7 1 97 44 0 100]
--------------- [ PASO 20 ] ---------------
97 > 44 = true
[6 28 34 23 61 2 7 1 44 97 0 100]
--------------- [ PASO 21 ] ---------------
97 > 0 = true
[6 28 34 23 61 2 7 1 44 0 97 100]
--------------- [ PASO 22 ] ---------------
97 > 100 = false
[6 28 34 23 61 2 7 1 44 0 97 100]
--------------- [ PASO 23 ] ---------------
6 > 28 = false
[6 28 34 23 61 2 7 1 44 0 97 100]
--------------- [ PASO 24 ] ---------------
28 > 34 = false
[6 28 34 23 61 2 7 1 44 0 97 100]
--------------- [ PASO 25 ] ---------------
34 > 23 = true
[6 28 23 34 61 2 7 1 44 0 97 100]
--------------- [ PASO 26 ] ---------------
34 > 61 = false
[6 28 23 34 61 2 7 1 44 0 97 100]
--------------- [ PASO 27 ] ---------------
61 > 2 = true
[6 28 23 34 2 61 7 1 44 0 97 100]
--------------- [ PASO 28 ] ---------------
61 > 7 = true
[6 28 23 34 2 7 61 1 44 0 97 100]
--------------- [ PASO 29 ] ---------------
61 > 1 = true
[6 28 23 34 2 7 1 61 44 0 97 100]
--------------- [ PASO 30 ] ---------------
61 > 44 = true
[6 28 23 34 2 7 1 44 61 0 97 100]
--------------- [ PASO 31 ] ---------------
61 > 0 = true
[6 28 23 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 32 ] ---------------
61 > 97 = false
[6 28 23 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 33 ] ---------------
97 > 100 = false
[6 28 23 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 34 ] ---------------
6 > 28 = false
[6 28 23 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 35 ] ---------------
28 > 23 = true
[6 23 28 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 36 ] ---------------
28 > 34 = false
[6 23 28 34 2 7 1 44 0 61 97 100]
--------------- [ PASO 37 ] ---------------
34 > 2 = true
[6 23 28 2 34 7 1 44 0 61 97 100]
--------------- [ PASO 38 ] ---------------
34 > 7 = true
[6 23 28 2 7 34 1 44 0 61 97 100]
--------------- [ PASO 39 ] ---------------
34 > 1 = true
[6 23 28 2 7 1 34 44 0 61 97 100]
--------------- [ PASO 40 ] ---------------
34 > 44 = false
[6 23 28 2 7 1 34 44 0 61 97 100]
--------------- [ PASO 41 ] ---------------
44 > 0 = true
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 42 ] ---------------
44 > 61 = false
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 43 ] ---------------
61 > 97 = false
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 44 ] ---------------
97 > 100 = false
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 45 ] ---------------
6 > 23 = false
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 46 ] ---------------
23 > 28 = false
[6 23 28 2 7 1 34 0 44 61 97 100]
--------------- [ PASO 47 ] ---------------
28 > 2 = true
[6 23 2 28 7 1 34 0 44 61 97 100]
--------------- [ PASO 48 ] ---------------
28 > 7 = true
[6 23 2 7 28 1 34 0 44 61 97 100]
--------------- [ PASO 49 ] ---------------
28 > 1 = true
[6 23 2 7 1 28 34 0 44 61 97 100]
--------------- [ PASO 50 ] ---------------
28 > 34 = false
[6 23 2 7 1 28 34 0 44 61 97 100]
--------------- [ PASO 51 ] ---------------
34 > 0 = true
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 52 ] ---------------
34 > 44 = false
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 53 ] ---------------
44 > 61 = false
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 54 ] ---------------
61 > 97 = false
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 55 ] ---------------
97 > 100 = false
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 56 ] ---------------
6 > 23 = false
[6 23 2 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 57 ] ---------------
23 > 2 = true
[6 2 23 7 1 28 0 34 44 61 97 100]
--------------- [ PASO 58 ] ---------------
23 > 7 = true
[6 2 7 23 1 28 0 34 44 61 97 100]
--------------- [ PASO 59 ] ---------------
23 > 1 = true
[6 2 7 1 23 28 0 34 44 61 97 100]
--------------- [ PASO 60 ] ---------------
23 > 28 = false
[6 2 7 1 23 28 0 34 44 61 97 100]
--------------- [ PASO 61 ] ---------------
28 > 0 = true
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 62 ] ---------------
28 > 34 = false
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 63 ] ---------------
34 > 44 = false
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 64 ] ---------------
44 > 61 = false
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 65 ] ---------------
61 > 97 = false
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 66 ] ---------------
97 > 100 = false
[6 2 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 67 ] ---------------
6 > 2 = true
[2 6 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 68 ] ---------------
6 > 7 = false
[2 6 7 1 23 0 28 34 44 61 97 100]
--------------- [ PASO 69 ] ---------------
7 > 1 = true
[2 6 1 7 23 0 28 34 44 61 97 100]
--------------- [ PASO 70 ] ---------------
7 > 23 = false
[2 6 1 7 23 0 28 34 44 61 97 100]
--------------- [ PASO 71 ] ---------------
23 > 0 = true
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 72 ] ---------------
23 > 28 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 73 ] ---------------
28 > 34 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 74 ] ---------------
34 > 44 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 75 ] ---------------
44 > 61 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 76 ] ---------------
61 > 97 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 77 ] ---------------
97 > 100 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 78 ] ---------------
2 > 6 = false
[2 6 1 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 79 ] ---------------
6 > 1 = true
[2 1 6 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 80 ] ---------------
6 > 7 = false
[2 1 6 7 0 23 28 34 44 61 97 100]
--------------- [ PASO 81 ] ---------------
7 > 0 = true
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 82 ] ---------------
7 > 23 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 83 ] ---------------
23 > 28 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 84 ] ---------------
28 > 34 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 85 ] ---------------
34 > 44 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 86 ] ---------------
44 > 61 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 87 ] ---------------
61 > 97 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 88 ] ---------------
97 > 100 = false
[2 1 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 89 ] ---------------
2 > 1 = true
[1 2 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 90 ] ---------------
2 > 6 = false
[1 2 6 0 7 23 28 34 44 61 97 100]
--------------- [ PASO 91 ] ---------------
6 > 0 = true
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 92 ] ---------------
6 > 7 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 93 ] ---------------
7 > 23 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 94 ] ---------------
23 > 28 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 95 ] ---------------
28 > 34 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 96 ] ---------------
34 > 44 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 97 ] ---------------
44 > 61 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 98 ] ---------------
61 > 97 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 99 ] ---------------
97 > 100 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 100 ] ---------------
1 > 2 = false
[1 2 0 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 101 ] ---------------
2 > 0 = true
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 102 ] ---------------
2 > 6 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 103 ] ---------------
6 > 7 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 104 ] ---------------
7 > 23 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 105 ] ---------------
23 > 28 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 106 ] ---------------
28 > 34 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 107 ] ---------------
34 > 44 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 108 ] ---------------
44 > 61 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 109 ] ---------------
61 > 97 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 110 ] ---------------
97 > 100 = false
[1 0 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 111 ] ---------------
1 > 0 = true
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 112 ] ---------------
1 > 2 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 113 ] ---------------
2 > 6 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 114 ] ---------------
6 > 7 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 115 ] ---------------
7 > 23 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 116 ] ---------------
23 > 28 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 117 ] ---------------
28 > 34 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 118 ] ---------------
34 > 44 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 119 ] ---------------
44 > 61 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 120 ] ---------------
61 > 97 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 121 ] ---------------
97 > 100 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 122 ] ---------------
0 > 1 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 123 ] ---------------
1 > 2 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 124 ] ---------------
2 > 6 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 125 ] ---------------
6 > 7 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 126 ] ---------------
7 > 23 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 127 ] ---------------
23 > 28 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 128 ] ---------------
28 > 34 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 129 ] ---------------
34 > 44 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 130 ] ---------------
44 > 61 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 131 ] ---------------
61 > 97 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
--------------- [ PASO 132 ] ---------------
97 > 100 = false
[0 1 2 6 7 23 28 34 44 61 97 100]
===========================================

RESULTADO: [0 1 2 6 7 23 28 34 44 61 97 100]