ZeroCho Blog

안녕하세요! 이번 시간에는 기수 정렬에 대해 알아보겠습니다. 계수 정렬과 헷갈리시면 안 돼요. 헷갈리면 라딕스 정렬이라고 부르세요. 계수 정렬은 카운팅 정렬이라고 하시고요.

기수 정렬도 대단히 빠릅니다. 자리수를 비교해서 정렬하는 방식인데요. 그래서 단점이라면 자리수가 없는 것들은 정렬할 수 없습니다. 예를 들면 부동소수점같은 경우가 있겠네요. 하지만 문자열과 정수는 거의 다 정렬할 수 있습니다. 

복잡도는 O(dn)인데요. d는 가장 큰 데이터의 자리수입니다. 예를 들면 가장 큰 수가 10000이면 자리수는 5니까 O(5n)이 됩니다. 어쨌든 그냥 n이기 때문에 빠릅니다. 예를 들어볼까요? 제 방법은 가장 작은 자리수부터 비교하는 LSD 방법입니다. 가장 큰 자리수부터 비교하는 방법은 MSD라고 불립니다.

[125, 383, 274, 96, 0, 9, 81, 72]
1의 자리수를 기준으로 정렬합니다.
[0], [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]
정렬 끝

볼 때마다 기발한 방법같다는 생각이 듭니다. 또한 같은 두 수가 있어도 순서가 섞이지 않는 안정 정렬입니다. 비교 정렬도 아니고요. 코드로 볼까요? 코드는 좀 복잡합니다.

var counter = [[]];
var radixLSD = function(array, d) {
  var mod = 10;
  for (var i = 0; i < d; i++, mod *= 10) { // mod는 현재 정렬 중인 자리수를 나타내는 것으로 10부터 해서 100, 1000, ...으로 커집니다.
    for (var j = 0; j < array.length; j++) {
      var 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));
    var pos = 0;
    for (var j = 0; j < counter.length; j++) { // counter에 저장한 묶음들(나머지 순서로 정렬됨)을 실제 배열에 반영해줍니다.
      var 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]

코드가 복잡해보이지만 원리는 간단합니다. 자리수별로 묶어주고, 그것을 실제 배열에 다시 반영하면 됩니다. 단점은 counter과 bucket처럼 추가적인 메모리가 필요하다는 겁니다. 하지만 단점을 상쇄할 정도로 빠른 성능을 보여주기 때문에 사용할 수만 있다면 사용하는 게 좋습니다.

다음 시간부터는 잠깐 자료구조에 대해 다루겠습니다!