Thuật toán sắp xếp nổi bọt (Bubble Sort)

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.

2. Ý tưởng

Ý tưởng chính của thuật toán là xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

3. Giải thuật
- Bước 1: i=1; //Phần tử đầu tiên
- Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ X[n] đến X[i]
- Bước 3: i=i+1
- Bước 4: 
* Nếu i < n, quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.

4. Mã ngôn ngữ C

void BubbleSort(int X[], int n)
{
   int i, j;
   for (i=0, i<n-1, i++)
      for (j=n-1, j>i, j--)
         if (X[j]<X[j-1])
            swap(X[j-1],X[j]);
}

5. Ví dụ
 X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6 

i=1, j=8, swap(X[j-1],X[j], ta có 7, 2, 5, 4, 1, 3, 6, 8 
i=1, j=7, không đổi chổ, ta có 7, 2, 5, 4, 1, 3, 6, 8 
i=1, j=6, không đổi chổ, ta có 7, 2, 5, 4, 1, 3, 6, 8 
i=1, j=5, swap(X[j-1],X[j], ta có 7, 2, 5, 1, 4, 3, 6, 8 
i=1, j=4, swap(X[j-1],X[j], ta có 7, 2, 1, 5, 4, 3, 6, 8 
i=1, j=3, swap(X[j-1],X[j], ta có 7, 1, 2, 5, 4, 3, 6, 8 
i=1, j=2, swap(X[j-1],X[j], ta có 1, 7, 2, 5, 4, 3, 6, 8 

i=2, thực hiện tương tự ta có 1, 2, 7, 3, 5, 4, 6, 8 
i=3, thực hiện tương tự ta có 1, 2, 3, 7, 4, 5, 6, 8
i=4, thực hiện tương tự ta có 1, 2, 3, 4, 7, 5, 6, 8 
i=5, thực hiện tương tự ta có 1, 2, 3, 4, 5, 7, 6, 8 
i=6, thực hiện tương tự ta có 1, 2, 3, 4, 5, 6, 7, 8 
i=7, thực hiện tương tự ta có 1, 2, 3, 4, 5, 6, 7, 8 
Cuối cùng ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.

6. Đánh giá giải thuật

Đối với giải thuật nổi bọt (Bubble Sort), số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh có thể ước lượng trong từng trường hợp sau: 

Tốt nhất: So sánh: n(n+1)/2 ; Hoán vị: 0 

Xấu nhất: So sánh: n(n-1)/2; Hoán vị: n(n-1)/2 

 7.Nhận xét
 *Bubble Sort có các khuyết điểm sau: không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần. Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm.
 *Thuật toán Shake Sort là thuât toán cải tiến từ Bubble Sort để khắc phục khuyết điểm của Bubble Sort.


Các thuật toán sắp xếp khác:

   [Thuật toán sắp xếp] Selection Sort

   [Thuật toán sắp xếp] Insertion Sort + Binary Insertion Sort

   [Thuật toán sắp xếp] Interchange Sort

   [Thuật toán đang xem] Bubble Sort

   [Thuật toán sắp xếp] Quick Sort