Algorithm - Counting Sort

오늘.. 수업시간에 이게 나왔는데.. ㅋ

제목 느낌상 어려울 것 같지는 않았는데 왠일인지 들어도 무슨 말인지 도통 이해가 가지 않아서..

왜 난 못 알아듣지를 왜 난 못알아듣지를 혼자 반복하다가.. 

잘 설명해 놓은 블로그가 있길래 포스팅합니다. (교수님이 설명을 어렵게 하신거였어요~ㅋㅋ)

카운팅소트의 특징은 안정적으로 정렬하므로.. 짬밥이 같은 숫자라도 순서를 잘 유지해서 정리 해준대요  :D


출처: http://redwave102.blog.me/80076259189

계수 정렬(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]을 감소시킨 후