[CS] 버킷 정렬(Bucket Sort)

버킷 정렬(bucket sort) 알고리즘의 개념

• 버킷 정렬은 분석 대상 데이터의 분포 특성을 활용함
• 시간 복잡도를 O(n) 수준으로 개선시키려는 것을 목적
• 버킷 정렬은 데이터가 특정 범위 내에 확률적으로 균등하게 분포한다고 가정할 수 있을 때 적용할 만한 기법

과정 설명

1. 데이터 n개가 주어졌을 때 데이터의 범위를 n개로 나누고 이에 해당하는 n개의 버킷을 만든다.
2. 각각의 데이터를 해당하는 버킷에 집어 넣는다. (C/C++등에서는 벡터/연결리스트를 사용하며 새로운 데이터는 벡터/ 연결리스트에 추가한다)
3. 버킷별로 정렬한다.
4. 이를 전체적으로 합친다.

버킷 정렬(bucket sort) C++ 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void bucket_sort(vector<float>& v) {
	vector<vector<float>> bucket;
	//데이터 n개가 주어졌을 때 데이터의 범위를 n개로 나누고 이에 해당하는 n개의 버킷을 만듬
	bucket.assign(v.size(), vector<float>());
	int max_v= *max_element(v.begin(), v.end());
	//각각의 데이터를 해당하는 버킷에 집어 넣는다
	for (int i = 0; i < v.size(); i++) {
		int idx = v[i] * v.size() / (max_v + 1);
		bucket[idx].push_back(v[i]);
	}
	int idx = 0;
	for (auto& b : bucket) { 
		//버킷별로 정렬
		sort(b.begin(), b.end());
		//이를 전체적으로 합친다.
		for (auto& e : b) {
			v[idx] = e;
			idx++;
		}
	}
}
int main()
{
	vector<float> v = { 10.2345,230.403,10.2345,5403,3020,1023,300.20,300 };
	bucket_sort(v);
	for (auto& e : v) {
		cout << e << endl;
	}
	return 0;
}

• 실수 값들을 효과적으로 정렬할때 유용한 정렬인 것 같다.