두 원소의 키 비교에 의한 정렬 방법이 아닌 정렬 알고리즘으로 기수정렬과 계수정렬이 있다.

1. 기수정렬(Radix Sort)

(1) 설명

• 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

(2) 방법

1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다.
2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.
3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.
4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.
   

(3) 구현

• 정렬할 자료들 : x0, x1, x2, x3, ... x(n-1)

• 정렬 자료의 최대 자리 개수 : d

• 진수 : r
  (각 자료의 가장 왼쪽 자릿수가 1번째 자릿수이고, 가장 오른쪽 자릿수가 d번째 자릿수이다.)

• LSD(Least Significant Digit) Radix Sort

for i in range(d, 0, -1):
   bin[0], bin[1], bin[2], ... bin[r-1]을 초기화
   for j in range(0, n, 1):
      xj의 i번째 자릿수의 digit을 검사하여 xj를 bin[digit]에 넣는다.
      
   bin[0]부터 bin[r-1]까지 원소들을 차례로 모은다.
   

시간복잡도 : O(d(n+r)) (자릿수가 고정되어있으므로 안정적인 정렬방식이다.)

2. 계수정렬(Counting Sort)

(1) 설명

• Counting Sort(계수정렬)은 숫자들간 비교를 하지 않고 정렬을 하는 알고리즘이다.

• 일일이 비교를 하지 않고 각 숫자가 몇 개인지 센 다음에 정렬을 하기 떄문에 시간복잡도는 O(n)이 나오게 된다.

• 다만, Counting sort는 모든 리스트에 적용을 할 수는 없고, 일정한 조건을 만족하는 리스트들에만 해당 알고리즘을 적용할 수 있다.

• 조건들은 다음과 같다:

  • 리스트 내의 모든 element들은 정수여야 한다
  • 리스트 내의 모든 element들의 범위는 0~k (k는 정수)여야 한다
  • k=O(n)으로 나타나질 수 있어야 한다

• O(n)이지만, 퀵정렬이나 병합정렬을 더 많이 사용하는 이유는 계수정렬은 각 숫자가 몇 번 나왔는지 세는 배열을 또 하나 만들지만 연속된 숫자가 아닌 1, 2, 3 그리고 갑자기 100이 나온다면 그 빈 공간에 해당하는 공간(메모리) 낭비가 생기기 때문이다.

(2) 방법

1. A : 정렬하고자 하는 리스트
2. B : 정렬 결과를 저장하는 리스트
3. C[i] : A에서 i보다 같거나 작은 수의 개수
4. n : A의 원소 개수
5. k : A의 원소 중 최댓값+1 (0까지 포함해야 하므로)

(3) 구현

Algorithm CountingSort(A, B, k)
   for i = 0 to k
       C[i] = 0;
   for j = 0 to n-1		// A원소를 C의 해당 인덱스에 쌓기
       C[A[j]] += 1
   for i = 0 to k-1
       C[i] = C[i] + C[i-1] // 누적해서 원소 값 쌓아 놓기 (B에서 인덱스에 활용하기 위함)
   for j = n-1 down to 0
      B[C[A[j]] -1] = A[j];
      C[A[j]] -= 1;
      

시간 복잡도

• 시간복잡도를 다 더하면 O(n+k)가 된다.

• 만약 k=O(n) 이면 counting sort의 시간복잡도는 O(n)이 된다.

• 정렬을 하는 것이 이렇게 빠를 수 있는 이유는 counting sort는 비교를 하지 않기 때문이다.

• 하지만, k의 값이 너무 커지면 일반 정렬 알고리즘보다 느려질 수 있는 단점이 있다. (그래서 병합 정렬 또는 힙 정렬을 많이 사용함)

• Counting sort는 기존 element들의 순서를 지키면서 정렬을 시키기 때문에 stable sort로 분류된다. 하지만, 추가적인 메모리를 요구하기 때문에 in-place 알고리즘은 아니다.

참고 : 어느 행인의 개발 블로그