카운팅 정렬 알고리즘(Counting Sort) / 계수 정렬

카운팅 정렬(Counting Sort)는 각 항목의 개수를 세어 저장해 두고, 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘 입니다. 오름, 내림차순 정렬과정, 시간 복잡도, 특징등에 대해서 알아보겠습니다 !

 

카운팅 정렬이란?

정렬하고 싶은 배열 항목들의 순서를 결정하기 위해 각 항목(요소)들이 몇 개씩 있는지 세어서 적절한 위치에 정렬하는 방법입니다.

각 항목의 개수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 알고리즘입니다.

 

예를 들어 배열 [1, 2, 3, 1, 5, 6]이 있다고 하면 1은 2개가 있고 나머지 원소들은 1개가 배열 내에 존재합니다. 그러므로 배열 내에서 가장 큰 수를 반드시 알아야합니다.

 

파이썬에는

1. 다른 리스트를 두고 인덱스로 기록하는 방법

2. 딕셔너리를 활용하여 Key-Value로 기록하는 방법

두 가지 방법으로 구현할 수 있습니다.

---

정렬 과정

Arr: 정렬할 데이터 배열

cnt_list: 카운팅 리스트 배열

answer: 정렬된 리스트 배열 (Arr 배열과 길이가 같은 배열)

 

1. 정렬할 데이터에서 각 항목들의 개수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 리스트에 저장

> Arr [3, 1, 2, 1, 4, 5]  / cnt_list [2, 1, 1, 1, 1]

0이 0개, 1이 2개, 2가 1개, 3이 1개, 4가 1개, 5가 1개 있다는 cnt_list 입니다.

 

2. 정렬된 집합에서 각 항목(요소)의 앞에 위치할 항목의 개수를 반영합니다.

즉 해당 요소 앞에 몇 개의 원소가 있는지 체크한다는 것입니다.

배열 요소들을 차례대로 더해주면 알 수 있습니다.

여기서 배열을 사용하지 않고 dict를 사용하여 구현할 수도 있습니다.

마찬가지로 key, value를 이용하여 체크해주면 됩니다.

> cnt_list [2, 3, 4, 5, 6] (오름차순)

> cnt_list [6, 4, 3, 2, 1] (내림차순) 내림차순은 역순으로 더해줍니다.

 

3. 데이터의 마지막 항목부터 원소를 정렬합니다.

오름차순을 예시로 들어보겠습니다.

Arr [3, 1, 2, 1, 4, 5]의 마지막 원소는 '5'입니다.

아래에서 말하는 인덱스는 cnt_list에서의 인덱스입니다. 배열에서 인덱스는 [해당숫자 - 1]로 표현합니다.

 

1) 마지막 원소는 5, 인덱스는 4입니다. cnt_list[5-1]의 값은 6입니다. answer의 6번째 위치에 5를 삽입하고 cnt_list값을 감소합니다.

answer = [0, 0, 0, 0, 0, 5]

 

2) 뒤에서 2번째 원소는 4, 인덱스는 3입니다. cnt_list[3]의 값은 5입니다. answer의 5번째 위치에 4를 삽입하고 cnt_list값을 감소합니다.

answer = [0, 0, 0, 0, 4, 5]

 

3) 뒤에서 3번째 원소는 1, 인덱스는 0입니다. cnt_list[0]의 값은 2입니다. answer의 2번째 위치에 1을 삽입하고 cnt_list값을 감소합니다.

answer = [0, 1, 0, 0, 4, 5]

 

4) 뒤에서 4번째 원소는 2, 인덱스는 1입니다. cnt_list[1]의 값은 3입니다. answer의 3번째 위치에 2를 삽입하고 cnt_list값을 감소합니다.

answer = [0, 1, 2, 0, 4, 5]

 

5) 뒤에서 5번째 원소는 1, 인덱스는 0입니다. 3번 과정에서 값을 감소하였기 때문에 cnt_list[0]의 값은 1입니다. answer의 1번째 위치에 1을 삽입하고 cnt_list값을 감소합니다.

answer = [1, 1, 2, 0, 4, 5]

 

6) 첫번째 원소는 3, 인덱스는 2입니다. cnt_list[2]의 값은 4입니다. answer의 4번째 위치에 3을 삽입하고 cnt_list값을 감소합니다.

answer = [1, 1, 2, 3, 4, 5]

 

오름차순으로 정렬이 완료된 answer 배열을 얻을 수 있습니다.

---

시간 복잡도와 특징

• n: 데이터 개수, k: 배열 내부에서 최대값
• 평균 수행시간: O(n+k)
• Bad Case: O(n+k)
• 즉 k의 값이 엄청나게 큰 경우에 엄청난 시간 손해가 발생한다.
• k값이 1억이 넘게되면 1초이상 걸리게 된다
• n >> k 인 경우에는 O(n)으로 해결할 수 있다
• 장점: 정렬하려는 수의 개수가 적을 때 빠르게 정렬할 수 있다.
• 단점: 추가적인 메모리 할당이 필요하고, 개수가 많아지면 성능이 굉장히 저하된다.

 

관련 문제: https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

알고리즘을 코드로 구현한 자료는 구글링하면 굉장히 쉽게 얻을 수 있기 때문에 따로 작성하지 않겠습니다 !