버킷 정렬은 크기 n의 배열을 특정 범위의 요소 값을 보유하는 k 버킷으로 분할하여 작동합니다.
그런 다음 이러한 버킷은 예상 입력 크기에 따라 선택할 수 있는 정렬 알고리즘을 사용하여 정렬됩니다.
이 알고리즘을 다음과 같이 설명할 수 있습니다. -
알고리즘:
Create the initial bucketSort function Create variables for i, min, max, and bucket size Find min and max value Create amount of buckets Push values to correct buckets Sort buckets
예시
이에 대한 코드는 -
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)); 출력
콘솔의 출력 -
[ 1, 4, 4, 6, 7, 32, 34, 34, 65, 78, 879, 6767 ]