계수 정렬(Counting Sort)

계수 정렬(Counting Sort) 의 개념 요약

각 원소의 개수를 세어 저장해두고, 그에 따라서 적절한 위치에 정렬하는 알고리즘이다. 

 

 

 

구체적인 개념

원소들의 순서를 결정하기 위해 배열에 각 원소가 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 방법이다.

 

각 원소의 개수를 기록하기 위해 정수로 인덱스 또는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 정렬 알고리즘이다. 

 

카운트 리스트를 위한 충분한 공간을 할당하려면 배열 내의 가장 큰 정수를 알아야 한다. 

 

 

 

예제 

 

step 0. 

가장 작은 데이터(0)부터 가장 큰 데이터(9)까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.

 

 

 

step 1.

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

 

 

 

step 2.

결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.