[정렬 알고리즘] 기수정렬 with C++

이번 장에서는 기수정렬에 대해 알아보자.

 

기본적인 내용은 위키피디아를 참고하였음!

 

https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

기수 정렬 - 위키백과, 우리 모두의 백과사전

 

기수 정렬(Radix sort)는 기수 별로 비교 없이 수행하는 정렬 알고리즘이다. 기수에는 다양한 자료를 사용할 수 있다.

 

여기서 기수는 크기가 유한하고 사전순으로 정렬할 수 있어야 한다.

 

기수의 예로는 정수(...., 0, 1, 2, 3, 4... )가 있다. 여기서는 기준 정도로 이해하면 된다.

 

이 기수를 기준으로 원소를 버킷에 집어넣기 때문에 비교 연산이 따로 없다. 

 

기수 정렬의 시간복잡도는 O(dn)이다. n은 키의 수 이고 d는 키의 길이를 의미한다.

 

간단한 수열에 대해 기수 정렬을 적용해보자.

 

 

다음과 같은 수열이 있다고 하자.

 

이제 이 수열을 버킷에다가 담을 것이다.

 

 

10진법을 따라 버킷은 0부터 9까지 총 10개가 존재한다. 키의 길이가 10 따라서 d = 10인 경우이다.

 

위 수열에 일의자리에만 빨간 불이 들어와있다. 일의 자리에 숫자들 각각에 대응해서 각 버킷에 담아준다.

 

170의 일의자리 숫자는 0이고 이를 0번 버킷에 담아준다.

 

45의 일의자리 숫자는 5이니 이를 5번 버킷에 담아주자.

 

75의 일의자리 숫자 역시 5이니 앞서 45의 경우처럼 5번 버킷에 담아준다.

2의 일의자리 숫자는 2, 2번 버킷으로 직행.

 

나머지 802, 24, 66에 대해서도 같은 방식으로 버킷에다가 차곡차곡 담아준 모습이다.

 

 

이를 다시 버킷의 맨 아래부터 순서대로 꺼내어 정렬해준다.

 

170을 꺼내주고,

이어서 90도 꺼내줄 것이다.

 

나머지도 같은 방법으로 모조리 꺼내준다.

 

일의 자리에 대해 수행한 결과가 나왔다.

 

1의 자리에 대해서만 오름차순으로 정렬된 수열

같은 원리로 이번엔 십의자리에 대해 과정을 수행한다.

 

10의 자리에 들어온 빨간불..!

- 2의 십의자리는 0 따라서 0번 버킷

- 802의 십의자리는 0 따라서 0번

- 170의 십의자리는 7 따라서 7번 버킷

- 90의 십의자리는 9 따라서 9번 버킷

동일하게 쭉 담아준다

 

일의자리때 처럼 이번엔 십의자리에 따라 다시 버킷의 맨 아래부터 순서대로 꺼내준다. ( 각 버킷에 한하여 넣은 순서대로 나옴 )

 

이제 백의자리에 대해서 동일하게 과정을 거치면 된다. 

 

거의 다 왔다.

백의 자리에 대해 각 버킷에 할당해주고~

다시 순서대로 쭉 꺼내서 정렬하니 

이렇게 짠 하고 정렬이 되었다!

 

이제 코드를 한번 작성해보자.