정렬 알고리즘 - 기수 정렬(Radix Sort)

http://yeols.com/80075364360

기수 정렬(Radix Sort)

 

• 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.
  
  
• 특수 정렬 알고리즘
• 비교 정렬
• 두 원소를 비교하는 정렬의 하한선은 Ω(nlogn)
  
  " 최악의 경우 정렬 시간이 θ(nlogn)보다 더 빠를 수는 없는가? "
  
  
• 그러나 원소들이 특수한 성질을 만족하면 O(n)정렬도 가능하다.
• 기수 정렬
  - 원소들이 모두 k 이하의 자리 수를 가졌을 때 (k: 상수)
  
  
• 기수 정렬의 개념
• 입력이 모두 K 이하의 자리 수를 가진 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당) 사용할 수 있는 방법
  
  
  
• θ(n)시간이 소요되는 알고리즘
  
  
• 기수 정렬 수행 과정 #1
• 원소들의 일의 자리부터 비교 후 정렬, 다음은 십의 자리를 비교 후 정렬 ...

 

• 기수 정렬의 수행 과정 #2
• 정렬되지 않은[69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 기수 정렬 방법으로 정렬하는 과정을 살펴보자.
• 키 값이 두 자리 십진수 이므로, 10개의 버킷을 사용하여 기수 정렬을 두 번 반복한다.

1. 초기 상태 : 큐(여러 개의 원소들이 일정한 순서로 나열된 자료 구조이며, 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있음)를 사용하여 0부터 9까지 10개의 버킷을 만든다.

 

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [1단계]

- 정렬할 원소의 일의 자리 값에 따라서 순서대로 버킷에 분배 -

 

 

2. 키 값의 일의 자리에 대해서 기수 정렬 수행 [2단계]

- 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

 

 

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [1단계]

 - 정렬할 원소의 십의 자리 값에 따라서 순서대로 버킷에 분배 -

 

 

3. 키 값의 십의 자리에 대해서 기수 정렬 수행 [2단계]

 - 버킷에 분배된 원소들을 순서대로 꺼내서 저장 -

 

• 기수 정렬 알고리즘 분석
• 메모리 사용공간
• 원소 n개에 대해서 n개의 메모리 공간 사용
• 기수 r 에 따라 버킷 공간이 추가로 필요
  
  
• 연산 시간
• 연산 시간은 정렬할 원소의 수 n 과 키 값의 자릿수 d 와 버킷의 수를 결정하는 기수 r 에 따라 달라진다.
  - 정렬할 원소 n 개를 r 개의 버킷에 분배하는 작업 : (n+r)
  - 이 작업을 자릿수 d 만큼 반복
  
  
• 수행할 전체 작업 : d(n+r)
• 시간 복잡도 : O(d(n+r))

  [출처] 정렬 알고리즘 - 기수 정렬(Radix Sort)|작성자 열쓰