이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌9 - Algorithm - 2년 전 등록 / 일 년 전 수정

기수 정렬(radix sort)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

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

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

복잡도는 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처럼 추가적인 메모리가 필요하는 겁니다. 하지만 단점을 상쇄할 정도로 빠른 성능을 보여주기 때문에 사용할 수만 있다면 사용하는 게 좋습니다.

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

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

3개의 댓글이 있습니다.
8달 전
http://palpit.tistory.com/129 해당링크에 구현된 예제와 비교해서 살펴봐주세요 자리수를 산출하는 부분에서 수정이 필요할 거 같습니다
8달 전
자리수를 산출하는 부분이 어딘지를 잘 모르겠습니다. 같은 radixLSD라도 구현하는 방법이 다르기 때문에 발생하는 차이 아닐까요
일 년 전
안녕하세요 선생님 궁금한게 있는데요 6번째 줄이 자리수를 나타낸다고 주석에 써있는데요
var bucket = parseInt(array[j] % mod); 에서 만약 array[j]가 125이고 mod가 10이라면
bucket은 125 / 10의 나머지인 5가 나오는데 어떻게해서 자리수가 나오는것이죠 ?
위 로직은 사실상 배열의 인덱스로 정렬되는 구조가 아닌가 싶은데 제가 또 이해를 잘 못한건지 궁금합니다.
일 년 전
아아 자리수가 아니라 자리수로 나눈 나머지입니다. 배열의 인덱스로 정렬된다는 것은 counter[bucket]의 키값을 의미하시는 건가요?
일 년 전
네 그렇습니다. bucket은 0이상의 정수를 나타내기때문에 인덱스라는 표현을 썼습니다.
2년 전
포스트 설명이 너무 잘되어있어서 보기 좋네요 ㅎ
2년 전
뒷 부분도 빠른 시일 내에 완성하도록 하겠습니다!