[정렬] -계수정렬

계수정렬

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다

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

- 모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N개고 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를

보장한다

- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하다

- 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문에, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬을 사용할 수 없다

-  앞서 다룬 알고리즘과 달리 직접 데이터의 값을 비교한 뒤 위치를 변경하며 정렬하는 비교 기반의 정렬 알고리즘이 아니다

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

 

 

 

 

STEP 0  먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.

현재 예시에서는 가장 큰 데이터가 9 이고 가장 작은 데이터가 0이다.

따라서 우리가 정렬할 데이터의 범위는 0부터9까지 이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다.

즉, 크기가 10인 리스트를 선언하면 된다. 처음에는 리스트의 모든 데이터가 0이되도록 초기화한다.
그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이완료된다

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

 

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

 

 

---------------------------------------반복------------------------------------

 

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

 

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

 

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

리스트에 저장된 데이터 자체가 정렬된 형태  그 자체라고 할 수 있다. 

정렬된 결과를 확인하고 싶다면, 리스트의 첫번 째 데이터 부터 하나씩 그 값 만큼 인덱스를 출력하면 된다.

예를 들면0 ' 인덱스의값이2 이므로0 을2 번출력하면 된다

그 결과는 아래와 같다.

 

 

 파이썬으로 구현한 계수정렬

# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

계수정렬의 시간 복잡도

 

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

앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 증가시키고, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있고, 항상 빠르게 동작한다

 

계수정렬의 공간 복잡도

때에 따라서 심각한 비효율성을 초래할 수 있다

예를 들어 데이터가 0과 999999 두 개만 존재한다고 하면, 이럴 때에도 리스트의 크기가 100만이 되도록 선언해야 한다.

그래서 항상 사용할 수 있는건 아니고 동일한 값을 가지는 데이터가 많을 때 적합하다.

즉, 데이터의 크기가 한정되어 있고, 데이터가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다

계수 정렬의 공간 복잡도는 O(N+K)이다