계수 정렬(Count sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
- 특정한 조건이란?
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
- 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.
- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
- 예) 0 이상 100이하인 데이터 정렬
계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 ‘모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언’해야 하기 때문이다. 예를 들어 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화해야 한다. 여기에서 1개를 더해주는 이유는 0부터 1,000,000까지는 1,000,001개의 수가 존재하기 때문이다.
계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다. 과정을 보면,
- 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성
- 리스트의 모든 데이터가 0이 되도록 초기화
- 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가하면 정렬 끝
- 결과적으로 각 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됨
- 리스트이 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 됨
[계수 정렬을 코드로 직접 구현]
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값을 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
계수 정렬의 시간 복잡도
데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 계수 정렬은
- 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킨다.
- 추후에 리스트의 각 인덱스에 해당한느 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 한다.
- 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
계수 정렬의 공간 복잡도
계수 정렬의 공간 복잡도는 O(N+K)이다. 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 데이터가 0과 999,999 단 2개만 존재한다고 가정해보자. 이럴 때에도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
코딩 테스트의 환경 특성상 정렬 문제에서의 데이터 개수는 1,000만개 미만으로 출제될 것이다.
ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의