Sắp xếp nổi bọt (Bubble Sort) là gì ?

Giải thuật sắp xếp nổi bọt là một phương pháp đơn giản trong việc sắp xếp dữ liệu. Nó hoạt động dựa trên việc so sánh các cặp phần tử liền kề và thay đổi thứ tự nếu chúng không theo đúng thứ tự.

Tuy nhiên, giải thuật sắp xếp nổi bọt không phù hợp với các tập dữ liệu lớn, vì độ phức tạp trong trường hợp xấu nhất và trung bình là Ο(n2), với n là số lượng phần tử trong danh sách.

Bạn đang xem: Sắp xếp nổi bọt (Bubble Sort) là gì ?

Mặc dù giải thuật này chậm hơn các phương pháp sắp xếp khác như đổi chỗ trực tiếp, nhưng nó lại bù đắp bằng cách chỉ đổi chỗ hai phần tử kề nhau, do đó số lần đổi chỗ nhiều hơn.

Ý tưởng và phương pháp thuật toán

Giải thuật sắp xếp nổi bọt được thực hiện bằng cách bắt đầu từ phần tử cuối của danh sách và so sánh với phần tử bên trái của nó. Nếu phần tử đang xét nhỏ hơn phần tử bên trái, chúng ta đổi chỗ hai phần tử để đưa nó về vị trí đúng. Tiếp tục làm như vậy cho đến khi sắp xếp tất cả các phần tử trong danh sách.

Cách thức thực hiện giải thuật sắp xếp nổi bọt

1. Bước 1: Đặt i=0 (đại diện cho phần tử đầu tiên).
2. Bước 2: Lần lượt so sánh và đổi chỗ các phần tử từ phải sang trái, bắt đầu từ a[n] đến a[i], với biến j=n-i. Lặp lại đến khi j > i.
3. Bước 3: Tăng i lên i=i+1.
4. Bước 4: Nếu i < n, quay lại Bước 2. Ngược lại, dừng lại vì danh sách đã được sắp xếp theo thứ tự.

Ví dụ và minh họa

Giả sử chúng ta có một dãy số A gồm các phần tử: 4 5 0 11 8 6 9. Hãy sử dụng giải thuật sắp xếp nổi bọt để sắp xếp lại dãy số này.

Xem thêm : Tổng hợp 30+ mẫu hình nền PowerPoint ngộ nghĩnh, dễ thương

Đầu tiên, ta thiết lập i=0 và j=6.

• Xét a[j-1] và a[j]: a6 và a5. Vì 6 < 9, nên không đổi chỗ và giữ nguyên vị trí. Tiếp theo, j=j-1.

• Tiếp theo, xét a[j-1] và a[j]: a5 và a4. Vì 8 > 6, ta đổi chỗ 6 và 8 để được dãy mới: 4 5 0 11 6 8 9. Sau đó, j=j-1.

• Tiếp tục như vậy cho đến khi j=i=0, chúng ta tăng biến i lên: i=i+1=1.

• Thiết lập lại j=6.

• Xem thêm : Toán tử trong C#

  Tiếp tục xét a[j-1] và a[j]: a6 và a5. Vì 9 > 8, ta không đổi chỗ và giữ nguyên dãy: 4 5 0 11 6 8 9. Sau đó, j=j-1.

• Tiếp tục như trên cho đến khi giảm j dần về 1. Dãy vẫn giữ nguyên như ban đầu. Sau đó, tăng i lên.

• Tiếp tục lặp lại quá trình cho tới khi i > n, ta dừng giải thuật và kết quả là dãy đã được sắp xếp theo thứ tự: 0 4 5 6 8 9 11.

Đoạn mã C++

Dưới đây là đoạn mã C++ để triển khai giải thuật sắp xếp nổi bọt:

void Sapxep(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]){
                swap(a[j], a[j - 1]);
            }
        }
    }
}

void swap(int &a, int &b) {
    int c = a;
    a = b;
    b = c;
}

Với đoạn mã trên, chúng ta có thể sử dụng hàm Sapxep để sắp xếp một mảng số nguyên theo giải thuật sắp xếp nổi bọt.

Với giải thuật này, chúng ta có thể sắp xếp dữ liệu một cách hiệu quả và nhanh chóng, mặc dù không phù hợp với việc sắp xếp các tập dữ liệu lớn.

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập