DAA - Sắp xếp bong bóng

Bubble Sort là một thuật toán sắp xếp cơ bản, hoạt động bằng cách trao đổi nhiều lần các phần tử liền kề, nếu cần. Khi không cần trao đổi, tệp sẽ được sắp xếp.

Đây là kỹ thuật đơn giản nhất trong số tất cả các thuật toán sắp xếp.

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]

Thực hiệ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; 
      } 
}

Phân tích

Ở đây, số lượng so sánh là

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

Rõ ràng, biểu đồ cho thấy n² bản chất của loại bong bóng.

Trong thuật toán này, số lượng so sánh không phụ thuộc vào tập dữ liệu, nghĩa là liệu các phần tử đầu vào được cung cấp có theo thứ tự được sắp xếp hay theo thứ tự ngược lại hoặc ngẫu nhiên hay không.

Yêu cầu bộ nhớ

Từ thuật toán đã nêu ở trên, rõ ràng là sắp xếp bong bóng không yêu cầu thêm bộ nhớ.

Thí dụ

Unsorted list:

5 2 1 4 3 7 6

1 ^st lặp:

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 lặp:

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

Không có sự thay đổi trong 3 ^thứ 4 ^thứ 5 ^thứ 6 ^thứ lặp đi lặp lại.

Cuối cùng,

the sorted list is

1 2 3 4 5 6 7