[Python][이코테] 계수 정렬

계수 정렬

계수 정렬(count sort)은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

 

사용하기 좋은 조건은

• 모든 데이터가 정수
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
• 모든 범위를 담을 수 있는 크기의 리스트(배열) 선언 필수

즉 정수 형태의 리스트를 정렬할 때 가장 빠른 속도로 정렬이 가능한 알고리즘이다.

 

계수 정렬의 특징은 앞의 세 가지 정렬(선택, 삽입, 퀵)처럼 직접 데이터의 값을 비교하는 방식이 아니다

-> 비교 기반의 정렬 알고리즘이 아님

 

사용

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

 

예를 들어서

 

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

 

리스트가 있으면 가장 큰 데이터는 9, 가장 작은 데이터는 0이다.

 

그러므로 0~9의 인덱스가 모든 범위를 포함할 수 있도로 길이 10인 리스트를 하나 선언한다.

 

1.

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	1	0	0

 

2.

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	0

 

3.

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	1

...

 

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

형태의 각 숫자가 몇 번 등장했는지 정리된 리스트가 만들어진다.

 

이후 각 리스트의 인덱스만큼 출력해주면 끝이다.

 

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

0 0

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

0 0 1 1 

 

...

 

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

위의 결괏값을 얻으며 정렬된 결과를 얻을 수 있다.

 

코드

# 6-5 정렬 계수 정렬
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=' ')

 

 

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 하면

 

시간 복잡도는 O(N+K)이다.

 

계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐 아니라

 

리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.

 

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 현존하는 정렬 알고리즘 중에

 

기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.