function mostDigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
자릿수 최댓값은 0에서 시작
nums에 반복문 수행하고 Math.max 사용
만약 0과 12를 넣을 경우 12 반환(항상 큰 수)
mostDigits([23,567,89,12234324,90])을 수행할 경우
23은 2
567은 3 이런식으로 쭉 감
12234324에서 8나옴
helper는 이렇게 3개임!_!
🐣 기수정렬 : 의사코드 및 구현
앞에서 살펴본 helper는 3개임
이제 헬퍼 메소드를 루프에 몇 번 호출하고 버킷을 만듦
과정
[1]
수 목록을 받는 함수를 정의 (기수 정렬 radix sort)
먼저 가장 큰 수가 몇 자리인지 알아내야 함
최댓 자릿수(mostDigit)을 사용하여 확인
만약 4일 경우, 루프 4번 수행
버킷에다 각각의 자릿수로 4번 정렬 필요하기 때문
네 번 수행하려면 0에서 1, 그 다음 2, 그 다음 3으로 진행
버킷은 빈 배열이며, 진행할 때마다, 각 자릿수에 버킷을 만듦
하위 배열이 10개 있는 배열 (0부터 9까지)
이 배열의 0번 인덱스는 빈 배열로 시작
루프를 수행할 때마다 각각의 수를 올바른 버킷에 넣음
kth 를 따르는데, kth 자릿수란 : 루프 k가 무엇이든 0에서 시작하며 각 수를 올바른 위치, 올바른 버킷 슬롯에 0 자리를 사용하여 분류하고 다음으로는 첫째자리, 둘쨋자리를 이용한다는 것
[2]
각 배열이 아니라 열개의 슬롯을 가진 하나의 큰 배열
10의 0번 위치에 각각 분류 getDigit 사용하여 각 해당 자릿수 위치에 넣기
그 다음 현재 위치한 순서를 사용하여 목록으로 재구성
새 배열로 합치려고 함
순서 유지하고 다음 과정 시작 [3]
루프는 두개
외곽루프는 4번 수행 0,1,2,3번 자리를 살펴봄
내부 루프는 목록의 각 수에 무언가를 실제로 수행(위치이동)
마지막에는 목록을 반환
구현
radix_sort.js
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}
radixSort([23,345,5467,12,2345,9852])
위에는 radixSort이고
mostDigits, digitCount, getDigit의 helper method를 포함한 전체 코드는 아래에!
전체 코드
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}
radixSort([23,345,5467,12,2345,9852])
첫 째로 헬퍼메소르를 가지고 기수 정렬 radixSort 함수를 정의
수 목록 nums를 받음
다음으로 가장 큰 수에 자릿수가 얼마나 있는지 파악 (mostDigits)
for문에 k 넣고 maxDigitCount최댓값 카운트까지
digitBuckets 변수에 빈 배열 작성
for nums.lenght만큼 돌리면서 getDigit을 통해 자릿수 위치 변경하면서 버켓에 push
