- 기수 정렬도 빠르고, 자릿수를 비교해서 정렬하는 방식이다. 그래서 단점이라면 자릿수가 없는 것들은 정렬할 수 없다.
- 시간 복잡도는 O(kn)이다.는 가장 큰 숫자의 자릿수이고, n은 입력 배열의 크기이다. ex) 가장 큰 수가 10000이면 자릿수는 5니까 O(5n)가 된다.
동작 예시
[125, 383, 274, 96, 0, 9, 81, 72][0], // 1의 자리수를 기준으로 정렬합니다.
[81],
[72],
[383],
[274],
[125],
[96],
[9][
// 10의 자리수를 기준으로 정렬합니다. 0이나 9 같은 것은 10의 자리수가 0이라고 생각하시면 됩니다.
(0, 9)
],
[125],
[72, 274],
[81, 383],
[96][
// 100의 자리수를 기준으로 정렬합니다.
(0, 9, 72, 81, 96)
],
[125, 274, 383];
// 정렬 끝구현
let counter = [[]];
let radixLSD = function (array, k) {
let mod = 10;
for (let i = 0; i < d; i++, mod *= 10) {
// mod는 현재 정렬 중인 자리수를 나타내는 것으로 10부터 해서 100, 1000, ...으로 커집니다.
for (let j = 0; j < array.length; j++) {
let bucket = parseInt(array[j] % mod); // 같은 그룹으로 묶일 나머지를 나타내는 부분입니다.
if (counter[bucket] == null) {
counter[bucket] = [];
}
counter[bucket].push(array[j]); // 나머지 별로 묶어줍니다.
console.log("bucket", bucket, counter[bucket]);
}
console.log(counter.slice(0));
let pos = 0;
for (let j = 0; j < counter.length; j++) {
// counter에 저장한 묶음들(나머지 순서로 정렬됨)을 실제 배열에 반영해줍니다.
let value = null;
if (counter[j] != null) {
while ((value = counter[j].shift()) != null) {
array[pos++] = value;
}
}
}
console.log(array);
}
return array;
};
radixLSD([125, 383, 274, 96, 0, 9, 81, 72], 3); // [0,9,72,81,96,125,274,383]