기수 정렬

이때까지의 정렬 방법들은 모두 레코드들을 비교하여 정렬한다. 따라서 비교가 불가능한 레코드들은 정렬할 수 없다. 기수 정렬은 레크드를 비교하지 않고도 정렬하는 방법이다. 기수 정렬은 입력 데이터에 대해 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 방법이다.

기수 정렬 수행 방법

기수 정렬은 다음과 같은 과정을 거쳐서 정렬을 수행한다. 예를 들어, 현재 가지고 있는 데이터 중 가장 큰 자릿수가 100의 자리라고 해보자.

각 데이터들의 1의 자리를 비교해서 같은 데이터끼리 모은다. 1의 자리가 작은 데이터들이 앞에 위치하게 되고 큰 숫자들이 뒤에 위치하게 된다.(오름차순 기준)
이때 같은 자릿수에 여러 데이터가 있을 경우에는 입력된 순서(나열된 순서)로 데이터를 모은다.
2번까지 과정을 마치면 1의 자리가 가장 작은 숫자부터 가장 큰 숫자 순으로 데이터들이 정렬된다.
이번에는 10의 자리가 같은 데이터끼리 오름차순으로 나열한다.
10보다 작은 숫자들은 배열에 위치했던 순서대로 새로운 정렬의 제일 앞에 위치하게 된다.
1이번에는 100의 자리가 같은 데이터끼리 오름차순으로 나열한다.
100보다 작은 숫자들은 배열의 제일 앞에서부터 순서대로 채운다.
데이터들의 최대 자릿수가 100의 자리이기 때문에 더 이상 진행하지 않고 종료한다.

Let’s dive into example!

이게 왜 되는거지? 예시를 보면 이게 왜 되는지 직관적으로 와닿는다. 예시를 풀어보자.

조금은 극단적인 구성이지만 위 배열을 기수정렬로 정렬해보자

Phase 1

먼저 각 데이터들을 1의 자리끼리 비교해서 정렬시킨다. 일반적으로 중간단계 역할을 하는 버킷(큐)을 만들어서 데이터들을 모아준다. 각 그림에서 10과 100은 1의자리 숫자가 0이기 때문에 함께 모았고, 10이 100보다 기존 배열에서 앞선 위치에 위치했기 때문에 더 앞에 왔다. 이제 1의 자리에 대한 정렬은 끝났다.

Phase 2

1의 자리까지 정렬된 배열을 가지고 이제 10의 자리를 기준으로 정렬해보자. 5와 8은 10자리가 존재하지 않기 때문에 버킷의 0번째 인덱스에 몰아주고 정렬된 배열을 만들 때는 들어간 순서대로 나열해준다.

Phase 3

마지막 100의 자리를 기준으로 정렬을 수행해보자. 100을 제외한 다른 데이터들은 100의 자리가 존재하지 않기 때문에 모두 버킷의 0번 인덱스로 순서대로 들어간다. 그리고 100은 1번째 인덱스에 자리잡게 된다. 이 데이터들을 순서대로 꺼내서 배열에 넣으면 정렬된 배열이 완성된다.

기수 정렬 분석

기수 정렬의 알고리즘은 Օ(dN) 이다. N은 데이터의 개수를 의미하고 d는 데이터들의 최대 자리수이다. 기수 정렬은 비교연산을 수행하지 않고 버킷에 데이터를 넣고 빼는 작업(N)을 최대 자릿수(d)만큼 만큼 반복하기 때문에 위와 같은 시간복잡도를 가지게된다.

그리고 기수정렬은 안정정렬 이다. 정렬 이후에도 중복된 값들은 자리가 뒤바뀌지 않는다.

마지막으로 기수정렬은 버킷이라는 추가적인 메모리 공간을 요구하게 된다. 그런데 더 큰 문제는 버킷의 크기를 모든 케이스에 맞게 딱 정의하기 어렵다는 것이다. 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10개의 공간이 필요하지만, 만약 알파벳을 정렬한다면 총 길이가 26인 버킷이 필요하다.