Ordenamiento de burbuja

Atención , esta página está siendo migrada a https://lwh-21.github.io/Algos/

Ordenación de burbuja

La Ordenación de burbuja 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.

Representación animada del ordenación de burbuja :

Representación animada del ordenación de burbuja

  1. PROCEDIMIENTO bubble_sort ( vector a[1:n])
  2. iteración ← 0
  3. REPETIR
  4.     permut ← FALSO
  5.     PARA i VARIANDO DE 1 HASTA n - 1 - iteración HACER
  6.         SI a[i] > a[i+1] ENTONCES
  7.             intercambiar a[i] Y a[i+1]
  8.             permut ← VERDADERO
  9.         FIN SI
  10.     FIN PARA
  11.     iteración ← iteración + 1
  12. MIENTRAS QUE permut = VERDADERO
  1. let bubble_sort vector =
  2.     let iteración= ref 1 and permutation = ref true in
  3.     while (!permutation = true) do
  4.         permutation := false;
  5.         iteración := !iteración + 1;
  6.         for actual = 0 to (Array.length vector) - !iteración do
  7.             if vector.(actual) > vector.(actual + 1) then
  8.             begin
  9.                 (* Intercambiamos los dos elementos *)
  10.                 permutation := true;
  11.                 let temp = vector.(actual) in
  12.                 begin
  13.                    vector.(actual) <- vector.(actual + 1);
  14.                    vector.(actual + 1) <- temp;
  15.                 end
  16.             end
  17.         done;
  18.     done;
  19. vector;;
  1. type tab = array[1..20] of integer;
  2. PROCEDIMIENTO bubble_sort(var vector : tab);
  3. var permutation : boolean;
  4.     actual : integer;
  5.     temp : integer;
  6.     iteración : integer;
  7.  
  8. begin
  9.     iteración := 1;
  10.     REPEAT
  11.         permutation := false;
  12.         for actual := 1 to 20 - iteración do
  13.         begin
  14.             if (vector[actual] > vector[actual + 1]) then
  15.             begin
  16.                 { Intercambiamos los dos elementos }
  17.                 temp := vector[actual];
  18.                 vector[actual]:=vector[actual + 1];
  19.                 vector[actual + 1]:=temp;
  20.                 permutation := true;
  21.             end;
  22.         end;
  23.         iteración := iteración + 1;
  24.     UNTIL (not permutation);
  25. end;
  1. def bubble_sort(vector):
  2.     permutation = True
  3.     iteración = 0
  4.     while permutation == True:
  5.         permutation = False
  6.         iteración = iteración + 1
  7.         for actual in range(0, len(vector) - iteración):
  8.             if vector[actual] > vector[actual + 1]:
  9.                 permutation = True
  10.                 # Intercambiamos los dos elementos
  11.                 vector[actual], vector[actual + 1] = \
  12.                 vector[actual + 1],vector[actual]
  13.     return vector  
  1. void bubble_sort(int* vector)
  2. {
  3.     int iteración = 0;
  4.     bool permutation = true;
  5.     int actual;
  6.    
  7.     while ( permutation) {
  8.         permutation = false;
  9.         iteración ++;
  10.         for (actual=0;actual<20-iteración;actual++) {
  11.             if (vector[actual]>vector[actual+1]){
  12.                 permutation = true;
  13.                 // Intercambiamos los dos elementos
  14.                 int temp = vector[actual];
  15.                 vector[actual] = vector[actual+1];
  16.                 vector[actual+1] = temp;
  17.             }
  18.         }
  19.     }
  20. }

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


Los siguientes gráficos muestran el aumento en el número de transacciones en relación con el número de elementos a ser ordenados.

Rendimiento del algoritmo

En el caso óptimo, con los datos ya ordenados, el algoritmo sólo effectura n comparaciones. Por lo tanto la complejidad en el caso óptimo es en Θ(n).

Rendimiento en el caso óptimo Número de operaciones Número de términos Θ(n)

En el caso desfavorable, con los datos ordenados a la inversa, la complejidad es en Θ(n2).

Rendimiento en el caso desfavorable Número de operaciones Número de términos Θ(n2)

En el caso medio, la complejidad de este algoritmo es también en Θ(n2)

Rendimiento en el caso medio Número de operaciones Número de términos Θ(n2)

Hay variantes interesantes del ordenamiento de burbuja como el Shaker sort, el ordonamiento de Oyelami o el Comb sort .