مرتب سازی سطلی (bucket sort) - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

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

+1 امتیاز
306 بازدید
سلام

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

ممنون
سوال شده اردیبهشت 11, 1394  بوسیله ی Azar (امتیاز 813)   4 18 58

1 پاسخ

+3 امتیاز
 
بهترین پاسخ

یکی از الگوریتم هایی هستش که مثل 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 هم هست.

 

پاسخ داده شده اردیبهشت 13, 1394 بوسیله ی BlueBlade (امتیاز 15,742)   13 17 85
ممنووون
چرا اگر من بازه را خودم مشخص کنم به این صورت
int bucket_range = ((Max-Min)/number_of_buckets)+1;
با مشکل مواجه میشم ؟
سلام ببخشید چند روز نبودم . اگر به اون شکل می خواهید بدست بیارید نیاز به +1 کردن نیست.
...