#014_자료구조와 알고리즘_count sort & radix sort

안녕하세요 삽잡이 입니다.

오늘은 카운트 정렬(count sort)와 기수 정렬(radix sort)에 대해서 알아보고자 합니다.

우선, count sort는 도수들의 개수를 파악합니다.

그 다음에 도수들을 배치할 수 있는 최대 범위를 구한 뒤 정렬을 진행 하는 것이지요.

우선 도수란 무엇일까요?

예전 중/고등학교 시절 수학시간에 들어본 말 아닌가요? 도수 분포표에서 말입니다.

도수란, 각 계급에 속하는 자료의 수라고 합니다.

예를 들어보자면 말입니다...

이와 같은 배열이 있다고 가정해보겠습니다. 이때 도수의 개수는 어떻게 될까요?

도수는 각 계급에 속하는 자료의 수라고 했습니다.

여기서 각 계급이란 a,b,c 라는 문자들이라고 볼 수 있겠군요.

그렇다면 도수의 개수는 아래와 같습니다.

자 그렇다면 count sort를 마저 진행해보도록 하겠습니다.

이제 도수의 개수까지 파악했으니 최대 범위를 구해보면 되겠군요...

생각해봅시다. 배열의 인덱스는 0부터 시작한다는 것을 감안했을때, 

a는 인덱스 0 ~ 1 까지 배치할 수 있습니다.

b는 인덱스 2 ~ 4, c는 5 ~ 7까지 배치할 수 있겠군요.

그렇다면 이 또한 아래와 같이 표현해보도록 하겠습니다.

그렇다면 이제 거의 끝났습니다. 도수의 최대 범위까지 정했으니 이제 정렬반 시키면 됩니다.

a, b, c 각각 인덱스 어느 부분까지 배치할 수 있는지 우리는 정리를 했습니다.

그렇다면, a, b, c 각각의 문자를 하나씩 배치할 때마다 

해당 문자의 최대 범위 인덱스를 하나씩 감소시켜준다면 정렬이 완료되겠지요.

자, 배열의 끝부터 하나씩 시작해보도록 하겠습니다.

문자 하나를 배치하면서 범위의 count가 하나씩 줄게 됩니다.

즉, 이제 다음 요소를 배치할 인덱스의 값이 나온 것이지요....

하나만 더 해볼까요?

이 처럼 하나씩 배치를 하다보면 결국은 아래와 같이 정렬이 완성됩니다.

count sort의 특징으로는,

자료의 개수가 자료의 종류수보다 클 때 전체 성능에 큰 영향을 미치지 않습니다.

또한, 배열의 크기만큼 추가적인 배열 하나가 더 필요하게 됩니다. 

따라서 count sort는 외부 정렬에 속하기도 하지요.

정렬하는 횟수는 총 n번 입니다. 즉 배열의 크기만큼 정렬하는 데 소요가 됩니다.

즉, 엄청나게 빠른 정렬이지요...

이름 그대로 quick 정렬이라는 분보다 훨씬 빠를 수 있다는...

하지만, count sort는 모든 곳에서 쓰일 수 있는 것이 아닙니다.

자료 개수가 자료 종류 수 보다 많을 경우 가능하며 (자료 수 > 자료 종류수),

이름 순으로 정렬할 때에는 사용을 하지 못합니다.

즉, 숫자 정렬이 가능하다는 것이지요...

다음으로 radix sort, 기수 정렬에 대해서 알아보도록 하겠습니다.

count 정렬을 이해하셨다면, 기수 정렬은 그다지 어렵지 않습니다.

기수 아시죠... 해병대? 허허... 아무튼,

제일 낮은 자리수 부터 count sort를 진행하고 

그 다음 자리수를 count sort...또 그다음 자리수를 count sort 하여 

결국은 가장 상위 자리수 까지 카운트 정렬을 진행한다면 전체 정렬이 되는 것입니다.

어렵지 않죠? 어렵지 않았길 바라며....

count sort, radix sort에 대해서 알아보는 것을 마치도록 하겠습니다.

이상 삽잡이였습니다~!