الگوریتم مرتب سازی سطلی (Bucket Sort)

الگوریتم مرتب سازی سطلی (Bucket Sort)

الگوریتم مرتب سازی سطلی (Bucket Sort) زمانی مناسب است که ورودی به صورت یکنواخت در یک رنج توزیع شده باشد. برای مثال مسئله زیر را در نظر بگیرید. مجموعه بزرگ اعداد اعشاری که در رنج ۰٫۰ تا ۱٫۱ قرار دارند و به صورت یکنواخت در آن رنج توزیع شده اند را مرتب کنید. یک روش ساده برای حل این مسئله استفاده از الگوریتم های مرتب سازی مبتنی بر مقایسه است. این گونه الگوریتم ها نمی توانند مسئله فوق را بهتر از nLogn مرتب کنند.

آیا می توانیم آرایه در زمان خطی مرتب کنیم؟ مرتب سازی شمارشی برای حل این مسئله کاربردی ندارد. چون در این الگوریتم از کلیدها به عنوان اندیس استفاده می شود، اما در اینجا کلیدهای به صورت اعداد اعشاری هستند. یک ایده مناسب استفاده از الگوریتم مرتب سازی سطلی است. در زیر الگوریتم مربوط به Bucket Sort را مشاهده می کنید:

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

پیاده سازی الگوریتم Bucket Sort

در زیر می توانید نحوه پیاده سازی الگوریتم مرتب سازی سطلی در زبان سی پلاس پلاس را مشاهده کنید:

// C++ program to sort an array using bucket sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
    // 1) Create n empty buckets
    vector<float> b[n];
    // 2) Put array elements in different buckets
    for (int i=0; i<n; i++)
    {
       int bi = n*arr[i]; // Index in bucket
       b[bi].push_back(arr[i]);
    }
    // 3) Sort individual buckets
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end());
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
          arr[index++] = b[i][j];
}
/* Driver program to test above funtion */
int main()
{
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr, n);
    cout << "Sorted array is \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

امتحان کنید

خروجی:

Sorted array is
0.1234 0.3434 0.565 0.656 0.665 0.897

نکات

• پیچیدگی زمانی در بدترین حالت برابر است با O(n²).
• پیچیدگی زمانی در حالت متوسط برابر است با O(n + k).
• پیچیدگی فضایی در بدترین حالت برابر است با O(n . k).

نوشته الگوریتم مرتب سازی سطلی (Bucket Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.