계수 정렬

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있는 알고리즘
• 매우 빠르다.
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
• 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야한다.
• ex) 가장 작은 데이터가 0, 가장 큰 데이터가 1,000,000이면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트 선언
• 앞 3가지의 정렬 알고리즘처럼 비교하는 비교 기반의 정렬 알고리즘이 아니다.

[과정]

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

리스트 내의 값들을 0으로 초기화 한다.

 

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

가장 앞에 있는 데이터부터 해당 데이터 값의 리스트 값을 +1한다.

 

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

 

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

이 과정을 반복해서 모든 데이터를 리스트에 적용시킨다.

 

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

결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다.

이제 이 리스트를 가지고 정렬된 데이터를 확인한다.

리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력한다.

 

[결과]

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

 

[소스코드]

data=[7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

r=max(data)-min(data)

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (r+1)

# 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(data)):
  count[data[i]-min(data)]+=1

# 리스트에 기록된 정렬 정보 확인 후 출력
for i in range(len(count)):
  for j in range(count[i]):
    p=i+min(data)
    print(p, end=' ')

 

[시간 복잡도]

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다.

 

[공간 복잡도]

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

예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정한다면, 이럴 때에도 리스트의 크기가 1,000,000가 되도록 선언해야한다. 

따라서 항상 사용할 수는 없고, 동일한 값을 가지는 데이터가 여러개 등장할 때 적합하다.(학생들의 성적 정렬)

앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하므로, 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.