مرتب سازی سطلی یک الگوریتم مرتب سازی است که با توزیع عناصر یک آرایه در تعدادی "سطل" عمل می کند. سپس هر سطل به صورت جداگانه مرتب می شود، یا با استفاده از الگوریتم مرتب سازی متفاوت یا به صورت بازگشتی با استفاده از الگوریتم مرتب سازی سطلی. در نهایت، سطل های مرتب شده برای تولید آرایه مرتب شده نهایی به هم متصل می شوند.
در اینجا توضیح گام به گام الگوریتم مرتب سازی سطلی آورده شده است:
1 - تعیین محدوده مقادیر در آرایه ای که باید مرتب شود: محدوده مقادیر برای تعیین تعداد سطل هایی که باید ایجاد شوند استفاده می شود. هر سطل حاوی عناصری با محدوده مقادیر مشابه خواهد بود.
2- Create the buckets: تعداد سطل ها با محدوده مقادیر تعیین می شود و هر سطل به عنوان یک آرایه جداگانه ایجاد می شود.
3- توزیع عناصر: هر عنصر از آرایه اصلی بر اساس مقدار خود در یک سطل مربوطه قرار می گیرد. به عنوان مثال، اگر محدوده مقادیر 0 تا 100 باشد و عنصر دارای مقدار 50 باشد، در سطل مربوط به محدوده 50-59 قرار می گیرد.
4- مرتب سازی هر سطل: هر سطل به صورت جداگانه مرتب می شود، یا با استفاده از الگوریتم مرتب سازی متفاوت یا به صورت بازگشتی با استفاده از الگوریتم مرتب سازی سطلی.
5- الحاق سطل های مرتب شده: سطل های مرتب شده برای تولید آرایه مرتب شده نهایی به هم متصل می شوند.
مرتب سازی سطلی دارای پیچیدگی زمانی O(n) است که عناصر به طور مساوی در بین سطل ها توزیع شوند. با این حال، اگر عناصر به طور مساوی توزیع نشده باشند، پیچیدگی زمانی الگوریتم می تواند O(n^2) شود اگر هر سطل به مرتب سازی جداگانه نیاز داشته باشد.
در نتیجه، مرتبسازی سطلی یک الگوریتم مرتبسازی ساده است که با تقسیم عناصر یک آرایه به تعدادی سطل، مرتبسازی هر سطل به صورت جداگانه، و سپس به هم پیوستن سطلهای مرتبشده برای تولید آرایه مرتبشده نهایی عمل میکند. در بهترین حالت پیچیدگی زمانی O(n) دارد که عناصر به طور مساوی توزیع شده باشند، اما می تواند پیچیدگی زمانی O(n^2) داشته باشد، زمانی که عناصر به طور مساوی توزیع نشده باشند.
c++:
#include <iostream>
#include <vector>
using namespace std;
void bucketSort(float arr[], int n) {
// Create n empty buckets
vector<float> b[n];
// 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]);
}
// Sort individual buckets
for (int i=0; i<n; i++)
sort(b[i].begin(), b[i].end());
// 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];
}
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;
}
python:
def bucket_sort(arr):
n = len(arr)
# Create n empty buckets
buckets = [[] for _ in range(n)]
# Put array elements in different buckets
for i in range(n):
bi = int(n * arr[i]) # Index in bucket
buckets[bi].append(arr[i])
# Sort individual buckets
for i in range(n):
buckets[i] = sorted(buckets[i])
# Concatenate all buckets into arr[]
index = 0
for i in range(n):
for j in range(len(buckets[i])):
arr[index] = buckets[i][j]
index += 1
return arr
# Example usage
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
result = bucket_sort(arr)
print("Sorted array is:", result)