버킷 정렬
버킷 정렬은 원소들이 균등 분포(Uniform Distribution) 일 때 유용하게 사용할 수 있는 정렬 알고리즘입니다.
버킷 정렬 알고리즘의 대략적인 흐름은 다음과 같습니다.
- [a, b] 범위의 원소들을 [0, 1)의 범위로 매핑시켜 준다.
- 각각의 원소들의 배열의 사이즈(n)를 곱하여 정수부만 취하여 인덱싱 해준다.(이때 0~n-1 인덱스 각각의 기댓값은 1로 균등하다.)
- 버킷 리스트(리스트 배열)에 인덱싱 된 값들을 매핑하여 넣어준다.
- 각각의 버킷을 부분 정렬한다.
- 정렬된 원소들을 원래 리스트에 복사해 준다.
이러한 버킷 정렬의 시간 복잡도는 Θ(n)로 이론상 매우 뛰어나지만 다른 Θ(nlogn) 정렬 알고리즘보다 조금 느린 정도의 퍼포먼스를 보여줍니다. 왜냐하면 버킷 리스트를 생성하고 관리하는데 드는 오버헤드가 만만치 않기 때문입니다. 또한 버킷 리스트를 만들기 위해 메모리를 동적으로 할당하게 이에 따른 메모리 부담도 상당합니다. 정수 데이터 1억 건을 버킷정렬하면 7.2GB 이상의 메모리 공간을 요구하게 됩니다.
버킷 리스트 없는 버킷 정렬(계수 정렬)
때문에 "버킷 리스트를 사용하지 않으면서 버킷 정렬을 구현할 수 없을까?"라는 생각을 하게 되었고 특정 원소 수를 세는 계수 정렬의 아이디어를 차용하여 버킷 인덱스의 개수를 세면 버킷 각각의 들어갈 원소의 개수를 알 수 있다는 것을 알게 되었습니다. 이를 기반으로 정렬할 리스트에서 각 버킷의 원소들이 들어갈 범위를 알 수 있어 그 부분만 부분 정렬을 하면 되게 됩니다.
그 과정을 정리해 보자면
- 버킷 정렬의 1~2 과정을 실행한다.
- 버킷 인덱스의 개수를 세어 배열 counts[]에 저장해 준다.
- counts[]의 누적합을 통해 각 버킷 인덱스의 시작 지점을 알려주는 start[]를 만들어 저장한다.
- start[]를 이용해 각 인덱스 별로 복사(각 인덱스 안의 범위는 아직 정렬 x) => 그냥 계수 정렬이라면 인덱스가 같으면 같은 값이므로 정렬이 완료됐다고 할 수 있겠지만 여기선 범위를 나누고 일정 범위 내의 원소들을 인덱스에 매핑시켜 준 것이므로 인덱스가 같은 부분끼리도 정렬이 필요
- 각 인덱스의 범위를 삽입 정렬을 이용하여 부분정렬
- 정렬이 완료된 배열을 원래 배열에 복사
위 과정을 자바를 통해 구현해 보겠습니다.
class BucketSortWithoutBuckets {
public static void bucketSort(int[] A) {
if (A.length == 0) return;
// 최대값 추출
int maxValue = A[0];
for (int i = 1; i < A.length; i++) {
if (A[i] >= maxValue)
maxValue = A[i];
}
// count[] Initialize
int bucketCount = A.length;
int[] counts = new int[bucketCount];
// 각 버킷 인덱스의 개수 세기
for (int i = 0; i < A.length; i++) {
int bucketIndex = (int)((float)(A[i] / (maxValue + 1)) * bucketCount); // [0,1)
counts[bucketIndex]++;
}
// 각 인덱스의 시작 지점 계산
int[] starts = new int[bucketCount];
starts[0] = 0;
for (int i = 1; i < bucketCount; i++) {
starts[i] = starts[i - 1] + counts[i - 1];
}
// 정렬한 결과를 담아 둘 배열 선언
int[] sortedArray = new int[A.length];
// 인덱스 별로 복사(각 인덱스 안의 부분은 정렬된 상태가 아님)
for (int i = 0; i < A.length; i++) {
int bucketIndex = (int) ((float)(A[i] / (maxValue + 1)) * bucketCount); // [0,1)
sortedArray[starts[bucketIndex]++] = A[i];
} //이 과정이 끝나면 starts[]는 다음 인덱스의 시작 지점을 가르키고 있음
// 각 인덱스 안의 범위를 부분 정렬
for (int i = 0; i < bucketCount; i++) {
int start = (i == 0) ? 0 : starts[i - 1];
int end = starts[i] - 1;
insertionSort(sortedArray, start, end);
}
// 원래 배열에 복사
for (int i = 0; i < sortedArray.length; i++) {
A[i] = sortedArray[i];
}
}
// 삽입 정렬을 이용해 부분 정렬 구현
private static void insertionSort(int[] A, int start, int end) {
for (int i = start + 1; i <= end; i++) {
int key = A[i];
int j = i - 1;
while (j >= start && A[j] > key) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = key;
}
}
public static void main(String[] args) {
int[] A = {29, 25, 3, 49, 9, 37, 21, 43, 44, 45, 46, 48, 50};
bucketSort(A);
System.out.println("Sorted array is: " + Arrays.toString(A));
}
}구현 결과 정상 작동하는 모습을 볼 수 있습니다. 속도는 데이터가 충분히 클 때 일반 버킷 정렬보다 조금 빠른 수준이지만 많은 메모리를 절약할 수 있다는 것이 장점입니다. 퀵 정렬과 비교했을 땐 퀵 정렬이 1.6~1.9배 빠르게 측정됐습니다.
버킷 정렬에 대해 공부하다가 계수 정렬이 0~k까지의 범위일 때 사용한다는 점과 버킷 정렬에서 인덱싱 과정에서 인덱스가 0~n-1로 형성된다는 공통점을 보고 이번 아이디어를 적용해 볼까 생각해 봤는데 진짜 적용이 돼서 신기했고 알고리즘적으로 많은 생각을 할 수 있는 시간이었던 것 같습니다. 또한 코드를 비판적으로 보고 개선할 수 있는 게 중요한 능력이라는 것을 깨닫게 되었습니다.
틀린 부분이 있다면 지적해주시면 감사하겠습니다.