Radix Sort 기수 정렬

 

Punch Card

Radix Sort 을 다루기 전에 Punch Card를 알아봅시다.
punch card는 한국어로 천공 카드인데요.

이게 바로 punch card입니다. 이게 프로그래밍의 시초인데요.
보다시피 숫자가 3자리씩 나열된걸 볼 수 있습니다.
이중 만약 백의 자리수는 2, 십의 자리수는 4, 일의 자리수는 1이  뚫려있다면 241이라는 숫자를 알게되는겁니다.
 
구멍을 뚫어서 숫자를 지정한 뒤 이걸 정렬하는 방식이 Radix Sort, 기수 정렬이었던겁니다.

각각 3자리 수를 구멍 뚫어서 만든 카드를 우린 0번부터 9번까지 정렬해야합니다.
이때 가장 큰 수는 맨 아래에, 가장 작은 수는 맨 위에 오도록 정렬해야합니다.
이때 이용하는 방식이 바로 기수 정렬입니다.
 

---

 

기수 정렬 (Radix Sort)

 

 
말로 설명하는것보다 눈으로 보는게 가장 편합니다.
보다시피 일의 자리수를 기준으로 먼저 가장 작은 수 부터 큰수까지 정렬해주고,
그다음 십의 자리수, 백의 자리수 까지 정렬해주면 됩니다.
그러면 우리는 3자리 수의 작은 수 부터 큰 수까지 정렬을 끝낸것과 같습니다.
 
 

패스 수에 대한 유도(의사 코드에서는 i)

숫자 1, 2, . . . , i − 1이 정렬됩니다.
숫자 i에 대한 안정적인 정렬이 정렬된 결과를 제공한다는 것을 입증해봅시다.
i 위치의 2자리 숫자가 다를 경우 i 위치순으로 정렬하는 것이 맞으며, 1, . . . , i − 1은 관련이 없습니다.
i 위치의 두 숫자가 같다면 숫자는 이미 올바른 순서로 되어 있는 것입니다(귀납적 가설에 따르면). 
따라서 숫자 i의 안정적인 정렬은 올바른 순서로 유지됩니다.

계산 정렬을 중간 정렬로 사용한다고 가정합니다.
패스당 Θ(n + k)(0, . . . , k 범위의 숫자)
d 패스
Θ(d(n + k)) 합계
k = O(n)이면 시간 = Θ(dn)입니다.
 
결론.  Θ(n) 시간 복잡도를 가집니다.
 

---

 
각 키를 숫자로 나누는 방법은 뭘까요?
 
1. n개의 단어(words)를 정렬합니다.
2. 각 단어는 b 비트로 구성됩니다.
3. 이를 r-비트 자릿수로 나눕니다. 이때 d = ⌈b/r⌉ (b를 r로 나눈 후 올림)입니다.
4. 계수 정렬을 사용하며, k = 2^r - 1 입니다. (r-비트로 표현할 수 있는 최대값)
5. 예시: 32-비트 단어를 8-비트 자릿수로 나누는 경우
   - b = 32, r = 8
   - d = 32/8 = 4 (4개의 자릿수로 나눔)
   - k = 2^8 - 1 = 255 (0부터 255까지의 값 가능)
6. 시간 복잡도: Θ((b/r)(n + 2^r))
   - b/r은 패스 횟수
   - n + 2^r은 각 패스에서의 계수 정렬 시간
 
Buckets Counts  = k = 2^r 부분이고
 
큰 키 값을 작은 자릿수로 나누어 효율적으로 정렬하는 기수 정렬의 원리였습니다.