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

Đây là bài 7/18 bài của series môn học Cấu trúc dữ liệu và giải thuật

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ử a0, a1, a2,…,an-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

Hoạt động của thuật toán sắp xếp nổi bọt (Bubble Sort)
Minh họa thuật toán Bubble Sort (Nguồn: codelearn.io)

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(n2).

5/5 - (2 bình chọn)
Bài trước và bài sau trong môn học<< Thuật toán sắp xếp chọn trực tiếp (Selection Sort)Thuật toán sắp xếp chèn trực tiếp (Insertion Sort) >>
Chia sẻ trên mạng xã hội:

Trả lời

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.