Cấu trúc dữ liệu và giải thuật: Giải thuật sắp xếp nổi bọt (Bubble sort)

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]);
}

5. Độ phức tạp của thuật toán

5 Likes

mình sài swap dc mà đúng hong anh

1 Like

đúng rồi bạn, xài thẳng swap luôn

Chỗ này phải dùng tham chiếu hoặc con trỏ mới tác dụng chứ bạn. Thao tác này ở biến local nên kết quả hoàn toàn như cũ. Bạn có thể thử chạy code của mình để kiểm tra.

3 Likes

Em cùng ý kiến với bác. Function này chạy xong không có tác dụng gì hết. Vì đây pass by value (truyền tham trị). Hàm doiCho khi thực thi sẽ tạo ra một stack frame (một vùng không gian riêng biệt) trên stack và chỉ copy giá trị của đối số vào biến local bên trong thân hàm. Cần truyền kiểu dữ liệu tham chiếu vào hàm doiCho.

3 Likes

Mình cảm ơn bạn và bạn bên dưới đã góp ý nha, mình còn quên text cả kiểu ‘int&’ vào, để mình sửa lại code.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?