기수 정렬

이번에 소개할 기수 정렬(Radix sort)도 지난번에 다룬 카운팅 정렬 처럼 두 요소의 대소관계 파악없이 진행하는 정렬법 입니다. 그리고 제가 기본적으로 소개할 기본적인 정렬방식의 마지막이기도 합니다.

---

1. 기수 정렬

기수 정렬은 요소의 대소 관계를 파악하지 않고 정렬하는 방식입니다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 요소의 최대 자릿수를 의미합니다. 즉, 정렬하려는 요소가 1의 자리라면 O(n)수준의 아주 빠른 시간 복잡도를 가질 것 이고, 1000, 10000의 자리 이런식으로 늘어날수록 시간 소모가 늘어납니다.

 

 

2. 기수 정렬의 동작 원리

기수 정렬은 각 요소를 분해해서 한자리 씩 비교합니다. 숫자라면 일의 자리는 일의 자리끼리, 문자열이라면 마지막 글자 끼리 비교합니다. 그 결과를 토대로 '버킷'이라고 하는 임시 분류 배열에 넣어둡니다. 그리고 다음 자리를 비교해나가며 크기대로 정렬하는 방식입니다.

다음과 같이 다양한 자릿수의 수가 들어있는 배열이 있습니다. 그리고 버킷이 있습니다. 버킷은 각 자리에 올 수 있는 수 십진수이므로 0~9까지의 칸을 만들어줍니다. 그림 편의상 버킷을 두 칸으로만 주었지만 실제로 버킷은 최대로 배열의 요소수 갯수 만큼 있어야 합니다.

이제 각 요소의 1의 자리끼리 비교해서 각 1의 자리가 나타내는 숫자에 해당하는 버킷에 넣어줍니다.

그리고 버킷에 담긴 순서대로 꺼내서 배열에 저장합니다.

이번에는 십의 자리를 비교해서 해당하는 버킷에 넣습니다. 만약 십의 자리가 없는 수라면 0버킷에 넣으면 됩니다.

이렇게 십의 자리까지 정렬된 수들을 배열에 옮겨 넣으면 정렬이 완료됩니다. 이 예시에서는 십의 자리까지만 있는 수들이어서 두 번만에 비교가 끝났지만, 백의 자리, 천의 자리라면, 이 과정을 세 번, 네 번 혹은 그 이상 반복하여 정렬된 결과를 얻을 수 있게됩니다.

 

 

 

3. 기수 정렬 구현

지난번 카운팅 정렬에 비하면 조금 더 복잡한 구현을 갖고 있습니다. 지난번과 마찬가지로 요소의 최대 자리수를 프로그래머가 알고 있다는 가정하에 인수로 넘겨와서 인자로 사용했지만 실제로 사용할 때는 maxDigit을 따로 구하는 함수를 사용해서 넘겨주는 것이 올바른 방식입니다.

export const radixSort = (arr, maxDigit) => {
    //정렬중인 자릿수를 나타내는 digit 변수
    let digit = 10;
    let counter = [[]];

    //요소의 최대 자릿수 만큼 비교과정을 반복합니다.
    for (let i = 0; i < maxDigit; i++) {
        let position = 0;
        
        digit *= 10;

        //배열의 요소를 버킷에 나눠 담는 반복문
        for (let j = 0; j < arr.length; j++) {
            //여기서 구해진 나머지가 버킷에 넣는 기준이 됩니다. 0~9
            let bucket = parseInt(arr[j] % digit);

            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            
            //구해진 나머지대로 버킷에 배열의 요소를 넣어줍니다.
            counter[bucket].push(arr[j]);
        }

        //버킷에 저장된 요소들을 순서대로 다시 배열에 넣어주는 정렬과정입니다.
        for (let j = 0; j < counter.length; j++) {
            let value = null;

            if (counter[j] != null) {
                while ((value = counter[j].shift()) != null) {
                    arr[position++] = value;
                }
            }
        }
    }
    return arr;
};

import {radixSort} from './study-code/sort/radix-sort.js';

let arr = [3, 17, 6, 46, 22, 13];

console.log(radixSort(arr, 2));

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/radix-sort.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록