[알고리즘] 기수정렬/ radix sort

📕기수정렬은 어떤 정렬인가

---

아마 card-sorting machine에 대해서 아는 사람은 드물 것이다. 

오래전 IBM에서 만든 컴퓨터는 펀치 카드를 사용해서 결과값을 출력했는데,

이 카드를 정렬하는 기계가 바로 card-sortin machine이다. 

그리고 이 기계에서 Radix sort를 사용했다!

 

 

 

📕LSD radix sort & MSD radix sort

---

LSD radix sort를 알려면, 먼저 LSD가 무엇인지 알아야한다.

 

LSD는 Least Significant Digit의 이니셜로 (환각물질 LSD가 아니다...)

LSD radix sort는 가장 아래자리의 문자 혹은 숫자부터 정렬하는 정렬 알고리즘이다.

반대로 앞에서 부터 정렬하는 MSD도 있다. (MSD의 M은 Most)

 

그렇다면 어떻게 정렬할까?

 

혹시 기수정렬의 다른 이름이 bucket sort라고 불리는 것을 아는가?

(기수정렬과 버킷정렬은 살짝 다르지만, 통용하고 있다.)

이렇게 불리는 이유는 바로 배열이라는 bucket에 넣어 정렬하기 떄문이다.

 

간단한 예제로 8, 2, 7, 3, 5 를 정렬해보자.

 

버킷에 넣기 위해서 숫자 8은 배열 인덱스 8에 저장하고, 2는 인덱스 2에 , 7은 7에, 3 은 3에 저장한다.

 

이를 정렬하면 배열을 순차적으로 출력했을때 가장 먼저 나오는 숫자는 무엇인가?

 

그렇다! 바로 2이다. 그 다음은? 3이다!

이러한 성질을 이용하여 코드를 구현하면 다음과 같다.

 

#include <iostream>

using namespace std;

int main() {
	int digit[6] = {8, 2, 7, 3, 6,};
    int bucket[10];
    
    for(int i =0; i < 6; i++) {
    	bucket[digit[i]] = digit[i];
    }
}

 

간단하지 않은가?!

 

그렇다면 두자리, 세자리 숫자는 어떻게 비교할까?

이때 MSD, LSD의 개념이 들어간다.

 

주로 모든 문자열, 숫자의 길이가 같은 경우 LSD를 사용하고, 다른경우 MSD 정렬을 사용하는데,

방법은 위와 비슷하다.(다만 key-index counting의 개념이 필요하다. 이는 후에 추가로 기술하겠다.)

 

LSD로 예를 들어 살펴본다면, 두자리 숫자의 경우

먼저 1의 자리 숫자를 1의 자리 숫자와 같은 배열 인덱스에 넣고

이를 차례대로 꺼낸 후, 다시 10의 자리 숫자를 위와 같은 방법으로 반복하는 것이다.

 

28, 93, 39, 81, 62, 72, 38, 26을 정렬한다면

 

1의 자리 숫자를 정렬한 후 순서는 81->62->72->93->26->28->38->39가 되고

 

10의 자리 숫자를 정렬한 후 순서는 오름차순으로 정렬될 것이다.

 

26, 28, 38, 39, 62, 72, 81, 93 과 같이 말이다. 

(코드로 따로 구현하진 않겠다.)

 

 

📕기수 정렬의 시간 복잡도

---

 

LSD 정렬은 key가 stable 할때만 사용할 수 있다. 모든 요소의 길이가 같은 경우처럼 말이다.

 

LSD정렬은 stable하고 

시간복잡도는 O(WN)으로 빠를 경우 선형시간에 근접한다.

그리고 추가공간 O(N + R)을 요구한다.

 

MSD정렬은 LSD와 반대로 정렬할 수 있는 문자의 경우 모두 정렬할 수 있다.

시간복잡도는 최선의 경우 O(2N)까지 가능하지만,(첫번째 인덱스가 모두 다를때)

최악의 경우O(2NW)이다. (모든 인풋이 같은 경우, W는 인풋의 길이)

랜덤한 inputd을 정렬할 경우 N * log(R)N만큼 걸리고, N+DR만큼의 공간복잡도를 요구한다.

 

시간복잡도를 통상적으로 O(d(n + bucket size))라고 생각하면 좋겠다.(d는 길이)