Chương trình C++ triển khai thuật toán Bucket Sort (Sắp xếp thùng)

Trong kỹ thuật Bucket Sort (Sắp xếp thùng), các mục dữ liệu được phân phối vào một tập hợp các thùng (buckets). Mỗi thùng có thể chứa loại dữ liệu tương tự. Sau khi phân phối, mỗi thùng được sắp xếp bằng một thuật toán sắp xếp khác. Sau đó, tất cả các phần tử được gom lại vào danh sách chính để có dạng đã sắp xếp.

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

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

Đầu vào — Danh sách dữ liệu chưa sắp xếp: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Đầu ra — Mảng sau khi sắp xếp: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

Thuật toán

bucketSort(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
        chèn array[i] vào thùng chỉ số (size * array[i])
    for i := 0 đến size-1
        sắp xếp bucket[i]
    for i := 0 đến size - 1
        gom các mục của bucket[i] và đặt vào mảng
Kết thúc

Mã ví dụ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

void bucketSort(float *array, int size) {
    vector<float> bucket[size];
    for(int i = 0; i < size; i++) {
        bucket[int(size * array[i])].push_back(array[i]);
    }
    for(int i = 0; i < size; i++) {
        sort(bucket[i].begin(), bucket[i].end());
    }
    int index = 0;
    for(int i = 0; i < size; i++) {
        while(!bucket[i].empty()) {
            array[index++] = *(bucket[i].begin());
            bucket[i].erase(bucket[i].begin());
        }
    }
}

int main() {
    int n;
    cout << "Nhập số lượng phần tử: ";
    cin >> n;
    float 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);
    bucketSort(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ử: 10
Nhập các phần tử: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Mảng trước khi sắp xếp: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Mảng sau khi sắp xếp: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79