정렬 알고리즘 - 계수 정렬(Counting Sort)

계수 정렬(Counting Sort)

 

• 특수 정렬 알고리즘(기수 정렬, 계수 정렬) 중 하나.
  
  
• 계수 정렬의 개념
• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘
  
  
• 속도가 빠르며 안정적이다.
  
  
• 제한 사항
• 정수나 정수로 표현할 수 있는 자료에 대해서만 동작
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

 

• 계수 정렬 수행 과정

• 1단계
  1. Data에서 각 항목들의 발생 횟수를 센다.
  2. 횟수들은 정수 항목들로 직접 인덱스 되는 카운트 배열 Counts에 저장

• 1단계
  3. 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위하여 카운트들을 조정한다.

• 2단계 : 정렬된 집합
  1. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

• 2단계 : 정렬된 집합
  2. Temp에 4을 삽입하고 Counts[4]을 감소시킨 후

• 2단계 : 정렬된 집합
  3. Temp에 2을 삽입하고 Counts[2]을 감소시킨 후

• 2단계 : 정렬된 집합
  4. Temp에 1을 삽입하고 Counts[1]을 감소시킨 후

• 2단계 : 정렬된 집합
  5. Temp에 3을 삽입하고 Counts[3]을 감소시킨 후

• 2단계 : 정렬된 집합
  6. Temp에 0을 삽입하고 Counts[0]을 감소시킨 후