Ordenando datos: Método de la burbuja

Quiero agradecer a quienes comentan tanto en el blog como en el canal de Youtube, muchas veces son ustedes los que me terminan marcando agenda y temas a tratar. En esta ocasión vamos a comenzar a hablar de métodos de ordenamiento con un clásico, el método de ordenamiento de burbuja (Bubble Sort).

El método

Supongamos que tenemos un vector de n elementos con diversos valores y queremos ordenarlo. Lo primero que hacemos es recorrer el vector con un ciclo For que va a ir desde el primer elemento hasta el último valor del vector (0 a n-2) . Un segundo For anidado va a recorrer también esos elementos. Este segundo For es el que va a ayudar con las comparaciones. Va a comparar el vector en el índice j con el j+1 y si el primero es mayor al segundo, entonces los invierte usando en medio una variable auxiliar.

Así como lo escribí parece un despelote, pero dejenme explicarme mejor con un poco de pseudocódigo:

Para i desde 0 a n-1
     Para j desde 0 a n-2
          Si vec[j]>vec[j+1] entonces
               aux=vec[j]
               vec[j]=vec[j+1]
               vec[j+1]=aux
          Fin Si
     Fin Para
Fin Para

Más o menos esto sería el famoso método, más sencillo visto así verdad? Obviamente por la red si se ponen a buscar van a encontrar montones de formas similares, todas válidas.

Ejemplifiquemos

Supongamos un vector = [5,8,2,3,10] y le aplicamos este algoritmo:

i=0

j=1 Intercambio 8 y 2

El vector queda: 5,2,8,3,10

j=2 Intercambio 8 y 3

El vector queda: 5,2,3,8,10

i=1

j=0 Intercambio 5 y 2

El vector queda: 2,5,3,8,10

j=1 Intercambio 5 y 3

El vector queda: 2,3,5,8,10

A partir de acá, el vector ya está ordenado, pero sin embargo, va a seguir haciendo comparaciones hasta finalizar el programa (i==n-1 y j==n-1)

Eficiencia

Como vimos, el método es muy pero muy sencillo de implementar en el lenguaje que se les ocurra, por lo que cualquier programador debería poder hacerlo rápido. El problema es que el algoritmo es altamente ineficiente, por la cantidad de comparaciones que tiene que hacer. Como vimos en el ejemplo, compara todo con todo y repite comparaciones ya realizadas. El ejemplo tenía solo cinco elementos, pero imaginen esto con una cantidad gigante de elementos (vamos a jugar con esto de los tiempos de ordenamientos en el futuro.

Hay algunas modificaciones que podemos hacerle a la burbuja que mejoran un poco su tiempo (en teoría) que las veremos en siguientes artículos pero es probada su ineficiencia.

Espero que les haya servido este artículo y como saben, siempre pueden contactarme y dejarme su parecer.

• 

•