계수 정렬 (Counting Sort)

계수 정렬 (Counting Sort)

 : 각각의 데이터가 몇 번씩 등장했는지를 세는 방식으로 동작하는 정렬 알고리즘

 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능한 정렬 알고리즘

 : 요소 값들끼리 서로 비교하지 않고 정렬 수행

 : 특정 조건 부합 시에만 사용 가능하지만, 특정 조건 만족 시 퀵 정렬보다도 빠르게 동작함

 : '배열 내 최대값 + 1' 길이의 배열 필요 -> 메모리 낭비 가능성 존재 ( = 상대적으로 공간 복잡도 높다)

 : 동일 값 가지는 데이터 여러 개 등장할 때 효과적

 

계수 정렬 동작 과정

1. 카운팅 배열 생성

 : 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 배열

 : 배열 내의 원소 값들의 개수를 저장하는 배열

 

2. 순회하며 각 데이터가 몇 번씩 등장했는지 횟수 count

 

3. 리스트의 첫 번째 데이터부터 하나씩 count 값만큼 반복하며 인덱스 출력

   -> 출력 결과가 정렬의 결과와 동일

 

계수 정렬의 시간 복잡도와 공간 복잡도

시간 복잡도 : O(N+K)

공간 복잡도 : O(N+K)

 

데이터의 개수(N)만큼 데이터를 하나씩 확인하며 등장 횟수를 세어줌

가장 큰 데이터 값인 K만큼, 각 인덱스를 확인하며 각 인덱스에 기록되어 있는 값 만큼 출력 수행