مرتب سازی سطلی (bucket sort)

Question

سلام

میشه یکی دقیق الگوریتم این مرتب سازی را توضیح بده ؟

ممنون

Answer 1

یکی از الگوریتم هایی هستش که مثل counting sort , radix sort برای مرتب سازی اعداد به کار میره و جا هایی استفاده میشه که اعضای آرایه به شکل یونیفرم بین 2 بازه خاص پخش شده باشن .

الگوریتم نسبتا راحتی هست اعضای آرایه رو به یکسری بازه خاص ( bucket )  تقسیم می کنیم این قسمت ها رو مرتب می کنیم . نهایتا اگر عناصر کنار هم گذاشته بشن آرایه مرتب بدست میاد . 

ویژگی اصلی  این الگوریتم cache friendly  بودنش هست . و برای آرایه های شامل اعضای یونیفرم با سایز بزرگ (بزرگتر از سایز cache ) سرعت خوبی داره . (چون مرتب سازی روی آرایه های کوچیکتر(bucket ها) انجام میشه و این آرایه ها می تونن بصورت کامل داخل cache قرار بگیرن ) .

شبه کد ویکیپدیا :

function bucketSort(array, n) is
    buckets ← new array of n empty lists
    for i = 0 to (length(array)-1) do
        insert array[i] into buckets[map_function(array[i], k)]
    for i = 0 to n - 1 do
        sort(buckets[i]);
    return the concatenation of buckets[0], ...., buckets[n-1]

کد :

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

const std::pair<int, int> range(0, 800);
const int bucket_range = 20;
std::vector<int> bucket_sort(const std::vector<int>& input){
	std::vector<int> res;
	res.reserve(input.size());
	
	const int number_of_buckets = (range.second - range.first) / bucket_range +1;
	std::vector<std::vector<int>> buckets(number_of_buckets);

	for (auto elem : input){//ferestadan anasor arraye be arraye haye koochiktar(bucket ha)
		buckets[elem/ bucket_range].push_back(elem);
	}
	for (auto& bucket : buckets){//moratab sazi bucket ha
		std::sort(bucket.begin(),bucket.end());//inja har alg sort dg ie ham mishod estefade kard
	}

	for (const auto& bucket : buckets){//etesal bucket ha be ham
		for (auto elem : bucket)
			res.push_back(elem);
	}
	return res;
}

int main(int argc, char** argv) {

	const int arr_size = 10000;
	//baraye tolid adad tasadofi ba tozi e uniform bein 0-800
	std::mt19937 generator;
	std::uniform_int_distribution<int> distribution(range.first, range.second);

	std::vector<int> rand_arr;
	rand_arr.reserve(arr_size);
	for (int i = 0; i < arr_size; i++){//por kardan array ba anasor random
		rand_arr.push_back(distribution(generator));
	}


	auto res= bucket_sort(rand_arr);

	for (auto elem : res)
		std::cout << elem << " ";
}

 

دقت کنید که اگر داخل مثال بالا طول بازه ها یعنی bucket_range رو  یک کنین این الگوریتم تبدیل به counting sort میشه . پس میشه گفت bucket sort حالت کلی تر counting sort هم هست.

 

Comments

ممنووون
چرا اگر من بازه را خودم مشخص کنم به این صورت
int bucket_range = ((Max-Min)/number_of_buckets)+1;
با مشکل مواجه میشم ؟

---

سلام ببخشید چند روز نبودم . اگر به اون شکل می خواهید بدست بیارید نیاز به +1 کردن نیست.

Answer 2

مرتب سازی سطلی یک الگوریتم مرتب سازی است که با توزیع عناصر یک آرایه در تعدادی "سطل" عمل می کند. سپس هر سطل به صورت جداگانه مرتب می شود، یا با استفاده از الگوریتم مرتب سازی متفاوت یا به صورت بازگشتی با استفاده از الگوریتم مرتب سازی سطلی. در نهایت، سطل های مرتب شده برای تولید آرایه مرتب شده نهایی به هم متصل می شوند.

 

در اینجا توضیح گام به گام الگوریتم مرتب سازی سطلی آورده شده است:

 

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)