Chương trình C++ triển khai thuật toán Bubble Sort (Sắp xếp nổi bọt)

Bubble Sort (Sắp xếp nổi bọt) là thuật toán sắp xếp dựa trên so sánh. Trong thuật toán này, các phần tử liền kề được so sánh và hoán đổi để tạo thành thứ tự đúng. Thuật toán này đơn giản hơn các thuật toán khác, nhưng cũng có nhược điểm. Thuật toán này không phù hợp cho tập dữ liệu lớn. Nó tốn nhiều thời gian để giải quyết các tác vụ sắp xếp.

Độ phức tạp của kỹ thuật Bubble Sort

• Độ phức tạp thời gian: O(n) cho trường hợp tốt nhất, O(n²) cho trường hợp trung bình và xấu nhất
• Độ phức tạp không gian: O(1)

Đầu vào — Danh sách dữ liệu chưa sắp xếp: 56 98 78 12 30 51
Đầu ra — Mảng sau khi sắp xếp: 12 30 51 56 78 98

Thuật toán

bubbleSort(array, size)

Đầu vào: Mảng dữ liệu, và tổng số phần tử trong mảng

Đầu ra: Mảng đã sắp xếp

Bắt đầu
    for i := 0 đến size-1
        flag := 0
        for j := 0 đến size - i - 1
            if array[j] > array[j+1] thì
                hoán đổi array[j] với array[j+1]
                flag := 1
        if flag ≠ 1 thì thoát vòng lặp.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void bubbleSort(int *array, int size) {
    for(int i = 0; i < size; i++) {
        int swaps = 0;
        for(int j = 0; j < size - i - 1; j++) {
            if(array[j] > array[j+1]) {
                swapping(array[j], array[j+1]);
                swaps = 1;
            }
        }
        if(!swaps)
            break;
    }
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    int arr[n];
    cout << "Nhập các phần tử:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Mảng trước khi sắp xếp: ";
    display(arr, n);
    bubbleSort(arr, n);
    cout << "Mảng sau khi sắp xếp: ";
    display(arr, n);
}

Kết quả đầu ra

Nhập số lượng phần tử: 6
Nhập các phần tử: 56 98 78 12 30 51
Mảng trước khi sắp xếp: 56 98 78 12 30 51
Mảng sau khi sắp xếp: 12 30 51 56 78 98