버킷 정렬(Bucket Sort)은 크기가 n인 배열을 요소 값의 특정 범위를 담는 k개의 버킷으로 나누어 정렬하는 알고리즘입니다.
배열이 여러 개의 버킷으로 분배되면, 각 버킷은 입력 데이터의 크기와 특성에 맞게 선택한 정렬 알고리즘(여기서는 삽입 정렬)을 사용해 개별적으로 정렬됩니다. 마지막으로 모든 버킷의 요소를 순서대로 이어 붙이면 전체 배열이 정렬된 상태가 됩니다.
버킷 정렬 알고리즘
이 알고리즘의 동작 과정은 다음과 같이 요약할 수 있습니다.
1. 초기 bucketSort 함수 생성 2. i, min, max, 버킷 크기(bucketSize) 변수 선언 3. 배열의 최솟값과 최댓값 탐색 4. 필요한 버킷의 개수 계산 5. 각 값을 알맞은 버킷에 배치 6. 각 버킷을 정렬한 뒤 하나로 합침
자바스크립트 구현 예제
다음은 자바스크립트로 버킷 정렬을 구현한 전체 코드입니다. 내부적으로 각 버킷을 정렬할 때는 삽입 정렬(insertion sort) 함수를 활용합니다.
const arr = [32, 6, 34, 4, 78, 1, 6767, 4, 65, 34, 879, 7];
const bucketSort = arr => {
if (arr.length === 0) {
return arr;
}
let i,
minValue = arr[0],
maxValue = arr[0],
bucketSize = 5;
arr.forEach(function (currentVal) {
if (currentVal < minValue) {
minValue = currentVal;
} else if (currentVal > maxValue) {
maxValue = currentVal;
}
})
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
let allBuckets = new Array(bucketCount);
for (i = 0; i < allBuckets.length; i++) {
allBuckets[i] = [];
}
arr.forEach(function (currentVal) {
allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
});
arr.length = 0;
allBuckets.forEach(function(bucket) {
insertion(bucket);
bucket.forEach(function (element) {
arr.push(element)
});
});
return arr;
}
const insertion = arr => {
let length = arr.length;
let i, j;
for(i = 1; i < length; i++) {
let temp = arr[i];
for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
return arr;
};
console.log(bucketSort(arr));
코드 동작 방식
- 최솟값·최댓값 탐색: forEach를 돌며 배열 전체에서 minValue와 maxValue를 구합니다.
- 버킷 개수 계산: (최댓값 − 최솟값) / bucketSize에 1을 더해 필요한 버킷 수를 결정합니다.
- 요소 분배: 각 값에 대해 (현재값 − 최솟값) / bucketSize 연산으로 해당 값이 속할 버킷 인덱스를 계산해 push합니다.
- 정렬 및 병합: 각 버킷을 삽입 정렬로 정렬한 후, 기존 배열(arr)을 비우고 정렬된 요소들을 순서대로 다시 채워 넣습니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
1, 4, 4, 6,
7, 32, 34, 34,
65, 78, 879, 6767
]
입력 배열이 오름차순으로 올바르게 정렬된 것을 확인할 수 있습니다. 버킷 정렬은 데이터가 고르게 분포되어 있을 때 평균 O(n + k)의 성능을 보이는 효율적인 정렬 방식입니다.