(이코테 w/ Python) 계수 정렬

계수 정렬이란? (Counting Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 

 

예시

출처: 유튜브 동빈나 채널

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

정렬할 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

 

배열에서 특정한 인덱스에 접근할 때 알고리즘 상으로 상수시간에 접근 가능하다고 보기 때문에

데이터를 하나씩 확인하며, 데이터와 동일한 인덱스에 카운트 값을 1씩 증가시키면서 해당 데이터가 몇 번 등장했는지 확인할 수 있다.

7부터 해당 데이터의 개수를 카운트한다. 

 

최종 리스트에 각 데이터가 몇 번씩 등장했는지의 횟수가 기록된다. 

 

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

 

전체 수행 결과는 정렬이 수행된 결과와 동일하다.

 

계수 정렬(counting sort)는 각각의 데이터가 몇 번씩 등장했는지 세는 방식으로 동작하는 정렬 알고리즘이다. 

가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 크기의 배열을 만들어야 하기 때문에 상대적으로 공간 복잡도가 높지만, 퀵 정렬과 비교했을 때 조건만 만족한다면 더 빠르게 동작한다. 

 

 

예시 코드

array = [...]

총 15개의 데이터가 리스트에 담겨있는 형태로 초기화한다.

 

count = [0] * (max(array) + 1)

모든 범위를 포함하는 리스트를 만든다. 이 때 모든 값은 0으로 초기화 할 수 있도록 한다.

현재 데이터는 0부터 9까지 구성되어 있어 9에 1을 더한 값인 10만큼의 크기를 갖는 하나의 카운트 배열을 만든다.

 

for i in range(len(array)):
	count[array[i]] += 1

데이터를 하나씩 확인하면서 데이터에 해당하는 인덱스의 값을 1씩 증가시킨다.

각 데이터가 몇 번씩 등장했는지 카운트 배열에 기록한 뒤에 (추후)리스트에 기록된 정렬 정보를 확인하면서 정렬을 수행한 결과를 출력할 수 있다. 

 

for i in range(len(count)):
	for j in range(count[i])):
    	print(o, end=' ')

인덱스 0부터 9까지 하나씩 확인하면서, 즉 각각의 인덱스를 전부 확인하면서

해당 인덱스를 값으로 갖는 데이터가(for j…) 몇 번씩 등장했는지 출력하도록 만들면 전체 데이터에 대해서 정렬 수행 결과가 나올 것이다. 

 

 

 

계수 정렬의 복잡도 분석

 

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)이다.

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.

 

예를 들어, 데이터가 0과 999,999로 단 2개만 존재한다고 가정해보자. 

데이터는 단 2개이지만, 백만개 만큼의 원소가 담길 수 있는 배열을 만들어야 한다. 

데이터의 범위가 크다면 계수 정렬을 사용하기 어렵다.

 

계수 정렬은 동일한 값을 갖는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다. 

성적의 경우 100점을 맞는 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다. 

데이터의 범위가 한정적이고 정렬할 데이터가 많기 때문에 계수 정렬이 적합하다.

 

출처: 유튜브 동빈나 채널

선택 정렬은 아이디어 뿐만 아니라 구현 또한 쉬운 편이다. 

퀵 정렬은 최악의 경우 O(N^2)이 나온다는 것을 명심해야 한다.

 

추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다. 

때문에 별도로 문제에서 정렬 함수를 구현하도록 요구하지 않는다면 표준 정렬 라이브러리를 호출하여 정렬을 수행하는 것이 좋다.