[Python] 계수 정렬 (Count sort)

계수 정렬은 특정한 조건에서 가능한 정렬 알고리즘이다.

특정한 조건만 만족한다면 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠른 알고리즘 중 하나이다.

계수 정렬의 시간 복잡도는 무려 O(N + K)이다. (N: 데이터의 개수, K: 데이터 중 최대값)

계수 정렬

계수 정렬의 조건

1. 데이터의 크기 범위가 제한된 경우
   
   • ex) 0 ~ 100 까지의 점수를 정렬하는 경우
2. 데이터가 양의 정수인 경우
   • 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함
3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않는 경우
   • 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐

 

계수 정렬의 정렬 방법

계수 정렬은 버블 정렬, 병합 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬 등의 비교 기반 정렬 알고리즘 과 다르게 직접 데이터의 값을 비교하지 않는다.

2021.03.07 - [C] 버블 정렬

2021.03.08 - [C] 숫자 애너그램 찾기 (다양한 정렬 알고리즘)

2021.03.15 - [C] linked list를 활용한 Merge Sort

2021.08.21 - [Python] Quick sort. 파이썬에서 간단히 퀵 정렬 구현

 

계수 정렬의 영어 표현은 [Count sort]이다. 말 그대로 Count 를 하는 것인데 그 방법은 다음과 같다.

1. 가장 큰 데이터와 가장 작은 데이터의 범위를 모두 담을 수 있는 리스트를 생성한다.
   • 가장 작은 데이터가 0, 가장 큰 데이터가 9일 때 크기가 10인 리스트를 선언하면 된다. (0~9 저장)
2. 1.에서 생성한 리스트를 0으로 초기화 한다.
3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
   • ex) 7이라는 데이터가 있다면 7번 인덱스의 값을 1 증가
4. 정렬 완료

 

주어진 데이터들

만약 위와 같은 데이터가 주어진다면 다음과 같은 리스트가 만들어질 것이다.

정렬 과정을 거쳐 만들어진 리스트

이렇게 만들어진 리스트를 순회하며 저장된 개수만큼 출력을 하면 다음과 같이 정렬이 완료된 모습을 볼 수 있다.

정렬 완료

이처럼 계수 정렬은 주어진 데이터가 양의 정수이며 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크지 않으면 동일한 데이터가 여러 번 등장하거나 데이터의 개수가 아주 많은 경우에 아주 효율적으로 정렬할 수 있는 정렬 알고리즘이다.