Giải thuật sắp xếp nổi bọt (Bubble sort)
1. Ý tưởng thuật toán
- Xuất phát từ cuối dãy, đổi chỗ các cặp nghịch thế nhằm đưa phần tử nhỏ hơn về đầu dãy hiện hành (nếu xếp tăng dần, giảm dần thì ngược lại), sau đó sẽ không xét đến nó ở bước 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 đã xét hết mọi cặp phần tử trong dãy.
Mình đã đề cập khái niệm nghịch thế trong topic Giải thuật sắp xếp Selection Sort.
2. Cơ chế hoạt động (sơ đồ dò vết)
Cho dãy số: | 5 | 2 | 3 | 1 | 4 |. Sắp xếp dãy số tăng dần.
-
Bước 1: i = 0;
j = 4, a[4] > a[3]; //không phải nghịch thế
j = 3, a[3] < a[2]; //nghịch thế
Đổi chỗ a[3] với a[2], ta được: | 5 | 2 | 1 | 3 | 4 |
j = 2, a[2] < a[1]; //nghịch thế
Đổi chỗ a[2] với a[1], ta được: | 5 | 1 | 2 | 3 | 4 |
j = 1, a[1] < a[0]; //nghịch thế
Đổi chỗ a[1] với a[0], ta được: | 1 | 5 | 2 | 3 | 4 |
j = 0 = i; —> i++;
Chỉ qua bước đầu, ta nhận thấy phần tử nhỏ nhất của dãy hiện hành “nổi lên” trên cùng, giống như tên của giải thuật này.
-
Bước 2: i = 1;
j = 4, a[4] > a[3]; //không phải nghịch thế
j = 3, a[3] > a[2]; //không phải nghịch thế
j = 2, a[2] < a[1]; //nghịch thế
Đổi chỗ a[2] với a[1], ta được: | 1 | 2 | 5 | 3 | 4 |
j = 1 = i; —> i++; -
Bước 3: i = 2
j = 4, a[4] > a[3]; //không phải nghịch thế
j = 3, a[3] < a[2]; //nghịch thế
Đổi chỗ a[3] với a[2], ta được: | 1 | 2 | 3 | 5 | 4 |
j = 2 = i; —> i++; -
Bước 4: i = 3
j = 4, a[4] < a[3]; //nghịch thế
Đổi chỗ a[4] với a[3], ta được: | 1 | 2 | 3 | 4 | 5 |
j = 3 = i; —> i++; -
Bước 5: i = 4
Đến đây, i không còn thỏa điều kiện, thuật toán dừng.
Ta thu được 1 dãy đã sắp xếp theo trật tự tăng: | 1 | 2 | 3 | 4 | 5 |
3. Các bước của thuật toán
Bước 1 : i = 0; //bắt đầu duyệt xuôi từ đầu dãy
Bước 2 : j = n-1; //mở vòng duyệt trong: duyệt từ cuối dãy ngược về vị trí i
-
Bước 2.1. Trong khi (j > i) thực hiện:
Nếu a[j] < a[j-1] gọi hàm doiCho(a[j], a[j-1]); - Bước 2.2. j = j - 1;
Bước 3 : i = i + 1; //duyệt xuôi ở lần xử lý kế tiếp
- Bước 3.1. Nếu i = n - 1: Hết dãy. Dừng.
- Bước 3.2. Ngược lại: Lặp lại Bước 2.
4. Cài đặt (C++)
void doiCho(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if(a[j] < a[j - 1]) doiCho(a[j], a[j - 1]);
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?