Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort)

Phân loại: Giải thuật sắp xếp ổn định.

Cấu trúc dữ liệu: Ngẫu nhiên.
Độ phức tạp thời gian (Time Complexity): Trường hợp xấu nhất (Worst Case) O(n²).

Độ phức tạp dung lượng (Space Complexity): O(1) vì nó chỉ sử dụng một số lượng không đáng kể bộ nhớ bổ sung cho các biến tạm thời như swapped, i, và j.

Độ phức tạp bộ nhớ (Memory Complexity): O(1) khi chỉ xét đến bộ nhớ bổ sung.

Đối với Bubble Sort, cả độ phức tạp dung lượng và độ phức tạp bộ nhớ đều là O(1), vì nó là một thuật toán tại chỗ (in-place algorithm) và không yêu cầu bộ nhớ bổ sung đáng kể ngoài bộ nhớ cho dữ liệu đầu vào.

Cách hoạt động:

1. Bắt đầu từ phần tử đầu tiên của mảng.
2. So sánh phần tử hiện tại với phần tử kế tiếp.
3. Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, hoán đổi chúng.
4. Di chuyển đến cặp phần tử kế tiếp và lặp lại bước 2-3 cho đến khi kết thúc mảng.
5. Lặp lại quá trình trên cho đến khi không còn phần tử nào cần hoán đổi trong toàn bộ mảng.

Pseudocode:

procedure bubbleSort(A : list of sortable items, n : integer)

    swapped := true // Biến kiểm tra xem có cần thực hiện thêm lần lặp nữa không

    for i from 0 to n-1 do // Lặp qua từng phần tử của mảng, bắt đầu từ phần tử đầu tiên

        if not swapped then // Nếu không có phép hoán đổi nào được thực hiện, dừng thuật toán

            break

        end if

        swapped := false // Đặt lại biến swapped thành false, chuẩn bị cho một lần lặp mới

        for j from 0 to n-i-1 do // Lặp qua từng cặp phần tử liên tiếp để so sánh và hoán đổi

            if A[j] > A[j+1] then // Nếu phần tử hiện tại lớn hơn phần tử kế tiếp

                swap(A[j], A[j+1]) // Hoán đổi hai phần tử

                swapped := true // Đánh dấu đã có phép hoán đổi được thực hiện

            end if

        end for

    end for

end procedure
 

Trong pseudocode này:

• A là danh sách các phần tử cần sắp xếp.
• n là số lượng phần tử trong danh sách.
• Chúng ta sử dụng biến swapped để đánh dấu xem có sự hoán đổi nào xảy ra trong một vòng lặp hay không.
• Thuật toán duyệt qua từng phần tử của danh sách và so sánh phần tử hiện tại với phần tử kế tiếp. Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, chúng ta hoán đổi chúng và đặt biến swapped thành true.
• Nếu không có sự hoán đổi nào xảy ra trong một vòng lặp, chúng ta dừng thuật toán vì danh sách đã được sắp xếp.

code C++:

#include <iostream>

        using namespace std;

        void bubbleSort(int arr[], int n) {

            bool swapped;

            for (int i = 0; i < n-1; i++) {

                swapped = false;

                for (int j = 0; j < n-i-1; j++) {

                    if (arr[j] > arr[j+1]) {

                        swap(arr[j], arr[j+1]);

                        swapped = true;

                    }

                }

                // Nếu không có sự hoán đổi nào xảy ra trong vòng lặp trong, dừng sắp xếp

                if (!swapped)

                    break;

            }

        }

        int main() {

            int arr[] = {64, 34, 25, 12, 22, 11, 90};

            int n = sizeof(arr)/sizeof(arr[0]);

            bubbleSort(arr, n);

            cout << "Sorted array: \n";

            for (int i = 0; i < n; i++)

                cout << arr[i] << " ";

            cout << endl;

            return 0;

        }