مرتب‌سازی سطلی (Bucket Sort) الگوریتمی غیرمقایسه‌ای است که عناصر را به تعدادی سطل تقسیم می‌کند و هر سطل را جداگانه مرتب می‌کند. این الگوریتم در حالت ایده‌آل دارای پیچیدگی زمانی $\mathcal{O}(n)$ است و در داده‌هایی که توزیع یکنواخت دارند، بسیار سریع عمل می‌کند.

ایده‌ی الگوریتم این است که مقادیر ورودی را به سطل‌های مختلف تقسیم کنیم و در نهایت هر سطل را مرتب کنیم. مراحل کلی الگوریتم به صورت زیر است:

‍۱. تعیین کمینه و بیشینه مقادیر داده‌ها.

۲. تقسیم بازه داده‌ها به سطل‌های مساوی.

۳. قراردادن هر عنصر در سطل مناسب.

۴. مرتب‌کردن هر سطل به صورت جداگانه (مثلاً با مرتب‌سازی درجی).

۵. الحاق تمام سطل‌ها برای بدست آوردن آرایه‌ی مرتب‌شده.

مثلاً آرایه‌ی $0.897, 0.565, 0.656, 0.123, 0.665, 0.343, 0.234, 0.456, 0.999$ را می‌توان در $10$ سطل قرار داد، سپس هر سطل را جداگانه مرتب کرد و در نهایت نتایج را ادغام نمود.

در بهترین حالت که عناصر یکنواخت پخش شده باشند و تعداد سطح‌ها از $\mathcal{O}(n)$ باشد زمان اجرا از $\mathcal{O}(n)$ است. اما در بدترین حالت همه عناصر ممکن است در یک سطل قرار بگیرند و از $\mathcal{O}(n^2)$ شود (اگر مرتب‌سازی هر سطل با مرتب‌سازی‌هایی مثل مرتب‌سازی درجی انجام شود).

bucket_sort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void bucketSort(vector<float> &arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);
    for (int i = 0; i < n; i++) {
        int index = n * arr[i];
        buckets[index].push_back(arr[i]);
    }
 
    for (int i = 0; i < n; i++)
        sort(buckets[i].begin(), buckets[i].end()); // O(n log n) sort
 
    int idx = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < buckets[i].size(); j++)
            arr[idx++] = buckets[i][j];
}
 
int main() {
    int n;
    cin >> n;
    vector<float> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i]; //between 0 and 1
    bucketSort(arr);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << ' ';
    cout << '\n';
 
    return 0;
}

*‌ مرتب‌سازی داده‌های یکنواخت (مثلا اعشاری بین ۰ و ۱).

* مرتب‌سازی سطلی - ویکی‌پدیا