이전까지의 정렬..

이제까지 쓴 버블, 삽입, 선택, 합병, 퀵 정렬의 경우 모두 비교 정렬 알고리즘에 속한다. 본질적으로 주어진 시점에서 두 개의 항목을 비교하여 정렬을 이루어낸다는 것이다. 그렇게 만들어진 정렬 중에 가장 나았던 정렬은 퀵, 합병 정렬로 시간복잡도가 $O (n l o g n)$ 이었다. 하지만 여기에서 더 빠른 정렬 알고리즘이 있을까?

답은 ‘있다’. 하지만 이건 비교를 통해 정렬을 이루어내는 방식이 아니다. 수학적으로 비교 정렬의 평균 시간 하한선은 $O (n l o g n)$ 이기 때문에 더 아래로 내려가는 것은 수학적인 제약이 있다.

그렇지만 비교가 아닌 다른 방식으로 정렬을 해서 이보다 더 줄일 수 있다! 대신 특정한 경우에 한정해서만 가능하긴 하지만 그런 빠른 정렬 알고리즘 중 하나가 기수정렬(Radix Sort) 이다.

기수 정렬이란?

기수 정렬은 우리가 저장하는 데이터가 이진 형식으로 되어있다는 점을 이용했다. 숫자 크기에 대한 정보를 자릿수대로 인코딩할 수 있다는 사실을 이용하여 자릿수 비교를 하는 방식이다.

[1556, 4, 3556, 593, 408, 4386, 902, 7, 8157, 86, 9637, 29]라는 배열이 있다고 해보자. 각 수는 한자리 수부터 4자리 수까지 있다.

여기에 우리는 0부터 9까지 각 수를 나타내는 10개의 버킷을 만든다. 각 요소는 제일 오른쪽 숫자를 기준으로 각각의 버킷에 들어간다.

마지막 일의자리 수로 버킷에 마구잡이로 넣어주었다. 이렇게 넣어놓은 버킷을 기준으로 0부터 9까지, 아래서부터 하나씩 빼가면서 다시금 배열에 저장한다. 정렬이 한번 되면 아래와 같이 숫자들의 일의자리 오름차순으로 정렬이 된다. [902, 593, 4, 1556, 3556, 4386, 86, 7, 8157, 9637, 408, 29] 이렇게 한 뒤 마지막 오른쪽에서부터 왼쪽으로 하나씩 자릿수를 높여가면서 다시금 정렬한다. 즉, 이번에는 십의자리 숫자대로 정렬하는 것이다.

십의 자리 순서대로 넣어주었다. 여기서 다음 자리수의 값이 없는 값들은 0으로 들어간다. [902, 4, 7, 408, 29, 9637, 1556, 3556, 8157, 4386, 86, 593] 다음으로 만들어진 정렬은 이와 같다. 계속해서 다음 백의자리 숫자, 다음은 천의자리 숫자.. 이렇게 늘려가면서 다음 자릿수의 수가 모두 없을 때까지 반복한다.

백의 자리 숫자로 다시급 정렬했다. 점점 정렬이 되어가는 것들을 볼 수 있다. [4, 7, 29, 86, 8157, 4386, 408, 1556, 3556, 593, 9637, 902] 백의 자리 숫자로 정렬했을 때의 결과는 이와 같다. 다시한번 돌려보자

천의자리로 정렬을 다시 하면 [4, 7, 29, 86, 408, 593, 902, 1556, 3556, 4386, 8157, 9637]의 순서대로 오게 된다. 제일 큰 수의 마지막 자리수까지 오게 되면 각 자리수 순서대로 아래서부터 뺐을 때 순서대로 정렬이 되어있는 것을 볼 수 있다.

이렇게 작동시키기 위해서는 각 요소의 수에서 해당 위치의 숫자를 알 수 있어야 한다.

구현

구현 과정에서 필요한 과정을 함수로 나누어 각각 구현해보았다.

getDigit

각 자릿수를 알아낼 수 있는 함수이다. 수와 위치를 가져온 다음 그 위치의 숫자를 반환할 수 있어야 한다.

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

digitCount

한 요소의 자릿수가 얼마인지 확인하는 함수

function digitCount(num) {
  if (num === 0) return 1;
  //들어오는 값에 대해 10의 제곱근을 구하고 1을 더함
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

mostDigits

각 요소중에서 자리수의 최대값을 리턴

function mostDigits(arr){
    let maxDigits = 0;
    for(let i=0;i<arr.length;i++){
        maxDigits= Math.max(maxDigits,digitCount(arr[i]))
    }
    return maxDigits
}

정렬

function radixSort(arr) {
  let maxLoop = mostDigits(arr);
  for (let i = 0; i < maxLoop; i++) {
    let bucket = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < arr.length; j++) {
      let place = getDigit(arr[j], i);
      bucket[place].push(arr[j]);
    }
    arr = [].concat(...bucket);
  }
}

시간복잡도

구분	시간복잡도
Average	$O (nk)$
Best Case	$O (nk)$
Worst Case	$O (nk)$
n의 경우 정렬할 항목 수나 정수의 수이고, k의 경우에는 이러한 수의 길이이다. 각 숫자의 자릿수를 의미한다.
평균과 베스트, 워스트 케이스가 모두 $O (nk)$ 로 같아 비교정렬보다 비슷하거나 빠르다.

🐢꾸준함의 미학

탐색기

정렬 - 기수정렬(Radix Sort)