[알고리즘] counting sort (계수 정렬)

소개

counting sort는 여러 정렬 알고리즘 중 하나로  n이 입력되었을 때, 문자열을 count해주는 부분에서 O(n) , result에 결과를 저장하는 부분에서 O(n), 출력부분에서 O(n)이 소요되어 Linear time( O(n) ) 안에 정렬을 끝낼 수 있다.

 

 

Pseudo code

 

동작과정

 

1.  입력배열 A, 수를 세기위한 배열 B, 결과를 저장하기 위한 배열 result가 필요하다.

 

 

 

2.  입력 배열A에서 나오는 수를 count하여 B에 저장해준다.

 

3.  이후 B배열을 누적하여 새로운 배열을 만든다.

          각 배열은, 정렬 시 해당 index가 몇번부터 시작하는지를 의미한다.

          (ex, B[2] = 4는 2가 result의 [4]부터 시작해서 앞 1 을 만날 때 까지 2를 채우면 된다는 의미이다.)

 

 

 

 

4.  A배열을 뒤에서부터 확인하며, 해당 숫자를 index로하여 B 배열을 확인해보면 그 수가 어디에 들어가야되는지 알 수 있다.

     

          이후, B의 요소를 1씩 줄여주어야 다음 수가 나왔을 경우 알맞은 자리에 넣을 수 있다.

 

 

 

 

www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html에서 애니메이션으로 counting sort를 확인할 수 있다.

 

 

 

 

 

해당 알고리즘을 사용한 예시는

knowable.tistory.com/14?category=910135. '1427'번 문제, c++ code

knowable.tistory.com/16?category=910135  '10989'번 문제

에서 확인할 수 있다.