Thuật toán Bucket Sort (Sắp xếp thùng)

Trong kỹ thuật Bucket Sort, các phần tử 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 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 thuật toán khác. Cuối cùng gom tất cả phần tử về mảng chính để có dạng đã sắp xếp.

Độ phức tạp Bucket Sort

• Time Complexity: O(n + k) tốt và trung bình, O(n²) xấu nhất
• Space Complexity: O(nk) xấu nhất

Input và Output

Input: Danh sách 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
Mảng trước sắp xếp: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Output: Mảng sau 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)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  for i := 0 to size-1 do
    insert array[i] vào bucket[index = size * array[i]]
  done
  for i := 0 to size-1 do
    sort bucket[i]
  done
  for i := 0 to size-1 do
    gom phần tử bucket[i] vào mảng
  done
End

Ví dụ (C++)

#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ố phần tử: "; cin >> n;
    float arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    bucketSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 10
Nhập phần tử: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Trước sắp xếp: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Sau sắp xếp: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

Đặc điểm: Bucket Sort hiệu quả khi dữ liệu phân bố đều (uniform distribution) trên [0,1). Dùng sort nội bộ (thường là Insertion Sort) cho mỗi bucket. Không ổn định tuỳ thuộc sort nội bộ.