DAA - Clasificación de burbujas

Bubble Sort es un algoritmo de clasificación elemental, que funciona intercambiando repetidamente elementos adyacentes, si es necesario. Cuando no se requieren intercambios, el archivo se ordena.

Ésta es la técnica más sencilla entre todos los algoritmos de clasificación.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementación

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Análisis

Aquí, el número de comparaciones es

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Claramente, el gráfico muestra el n² naturaleza del tipo de burbuja.

En este algoritmo, el número de comparación es independiente del conjunto de datos, es decir, si los elementos de entrada proporcionados están ordenados o en orden inverso o aleatorio.

Requisito de memoria

A partir del algoritmo indicado anteriormente, está claro que la clasificación de burbujas no requiere memoria adicional.

Ejemplo

Unsorted list:

5 2 1 4 3 7 6

1 ^st iteración:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2 ^nd iteración:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

No hay cambios en la ^3ª , ^4ª , ^5ª y ^6ª iteración.

Finalmente,

the sorted list is

1 2 3 4 5 6 7