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

1. Ý tưởng thuật toán sắp xếp nổi bọt

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a₀, a₁, a₂,…,a_n-1.

Xuất phát từ cuối danh sách, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về đúng vị trí theo thứ tự tăng dần. Cuối cùng, phần tử đầu tiên trong danh sách sẽ là phần tử nhỏ nhất.

Sau đó, sẽ không xét đến phần tử đầu tiên đó nữa ở bước tiếp theo. Do vậy, ở lần xử lý thứ i, phần tử đầu được xét sẽ có vị trí là i.

Lặp lại các bước xử lý trên cho đến khi không còn cặp phần tử nào để xét.

2. Các bước thực hiện thuật toán

Bước 1: i = 0;//lần xử lý đầu tiên

Bước 2: j = n-1;//duyệt từ cuối dãy ngược về vị trí i

Trong khi (j > i) xét trường hợp: Nếu a[j]<a[j-1] thì đổi chổ a[j] và a[j-1].

j = j-1;

Bước 3: i = i+1; //lần xử lý kế tiếp

Nếu i = n-1 -> hết dãy -> Dừng.

Ngược lại -> Lặp lại Bước 2.

Minh họa thuật toán sắp xếp nổi bọt

3. Cài đặt thuật toán sắp xếp nổi bọt với C++

#include <iostream>
using namespace std;
void Bubble_Sort(int a[],int n){
	int i, j;
	for (i=0; i<n-1; i++){
		for (j=n-1; j>i; j--){
			if(a[j]<a[j-1]){//nếu sai vị trí thì đổi chỗ
				swap(a[j], a[j-1]);
			}
		}
	}
}

void main()
{
	int a[5] = {8, 4, 1, 6, 5};
	Bubble_Sort(a, 5);
	cout<<"Mang sau khi sap xep:"<<endl;
	for(int i=0;i<5;i++){
		cout<<a[i]<<" ";
	}
	system("pause");
}

Kết quả

Mang sau khi sap xep:
1 4 5 6 8

Đánh giá giải thuật

Số phép so sánh trong trường hợp tốt nhất hoặc xấu nhất đều là n(n-1)/2. Độ phức tạp thuật toán là O(n²).