버킷 정렬(Bucket Sort)은 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다.
function bucketSort(arr: number[]): void {
const MAX = 100000; // 배열에 100000 미만 값만 존재한다고 가정
const N = arr.length;
// 각 요소의 개수를 카운트함
// num[v]: v 개수
const num = new Array(MAX).fill(0);
for (let i = 0; i < N; ++i) {
++num[arr[i]]; // arr[i]를 카운트
}
// num 누적합
// sum[v]: v 이하 값의 개수
// arr[i]가 전체에서 몇 번째로 작은 값인지 구하기
const sum = new Array(MAX).fill(0);
sum[0] = num[0];
for (let v = 1; v < MAX; ++v) {
sum[v] = sum[v - 1] + num[v];
}
// sum을 바탕으로 정렬
// sortedArr : arr를 정렬한 것
const sortedArr = new Array(N);
for (let i = N - 1; i >= 0; --i) {
sortedArr[--sum[arr[i]]] = arr[i];
}
// 원본 배열에 정렬 결과 반영
arr = sortedArr;
}
// main 함수 역할
function main() {
// 입력
const input = prompt("Enter the size of the array and its elements:");
if (!input) return;
const [N, ...elements] = input.split(" ").map(Number);
const arr = elements.slice(0, N);
// 버킷 정렬
bucketSort(arr);
// 출력
console.log("Sorted array:", arr.join(" "));
}
// 실행
main();
입력 데이터의 범위를 확인하고 적절한 수의 버킷(배열)을 생성합니다.
각 요소의 개수를 카운트합니다.
const num = new Array(MAX).fill(0);
for (let i = 0; i < N; ++i) {
++num[arr[i]]; // arr[i]를 카운트
}
arr = [ 3, 4, 7, 1, 3 ]
num[3] = 1개
num[4] = 1개
num[7] = 1개
num[1] = 1개
num[3] = 2개
—> N번
num 누적합을 구합니다. (arr[i]가 전체에서 몇 번째로 작은 값인지 구하기)
const sum = new Array(MAX).fill(0);
sum[0] = num[0];
for (let v = 1; v < MAX; ++v) {
sum[v] = sum[v - 1] + num[v];
}
sum[0] = num[0]; 0
v가 1일때 , sum[1] = sum[0] + num[1]; 0 + 1 = 1
v가 2일때 , sum[2] = sum[1] + num[2]; 1 + 0 = 1
v가 3일때 , sum[3] = sum[2] + num[3]; 1 + 2 = 3
v가 4일때 , sum[4] = sum[3] + num[4]; 3 + 1 = 4
.
.
v가 7일때 , sum[7] = sum[6] + num[7]; 4 + 1 = 5
—> A번
sum을 바탕으로 정렬합니다.
const sortedArr = new Array(N);
for (let i = N - 1; i >= 0; --i) {
sortedArr[--sum[arr[i]]] = arr[i];
}
i 가 4일 때, sortedArr[—sum[arr[4]]] = arr[4]; sortedArr[2] = 3 , sum[3] = 3 → sum[3] = 2
i 가 3일 때, sortedArr[—sum[arr[3]]] = arr[3]; sortedArr[0] = 1
i 가 2일 때, sortedArr[—sum[arr[2]]] = arr[2]; sortedArr[4] = 7
i 가 1일 때, sortedArr[—sum[arr[1]]] = arr[1]; sortedArr[3] = 4
i 가 0일 때, sortedArr[—sum[arr[0]]] = arr[0]; sortedArr[1] = 3
sortedArr = [1, 3, 3, 4, 7]
정렬 끝