카운팅정렬[counting sort]

카운팅정렬이란

항목들의 순서로 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여, 선형시간에 정렬하는 효울적인 알고리즘이다.

 

카운팅정렬은 기본적인 요소가 갖추어져야 하는 정렬인데..

1. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이가능. (각 항목의 발생횟수를 기록하기 위해, 정수항목으로 index되는 카운트들의 배열을 사용하기 때문)
2. 카운트들을 위핸 충분한 공간을 항당하려면 집합 내의 가장 큰 정수를 알아야함.

시간복잡도: O(n+k) (여기서 n은 배열의 길이, k는 정수의 최댓값이다.)

---

정렬 전 준비물:

1.주어진값(data)

2. data에 가장 큰 원소+1 의 리스트(counts)

3. data와 같은 크기의 리스트(temp)

 

 

정렬과정

 

1. 주어진 data의 최댓값만큼 count를 셀 배열(임의로 counts라 칭하겠음)을 만들어 data의 값에 맞는 index에 +1을 해준다.

 

2.count된 (counts)배열을 ++ 해주면서 중복값들로 변환시켜준다.

 

3. 주어진 data배열을 뒤에서부터 세어준다.

 

4. 뒤에서부터 세어진 data원소가 count된 counts 의 index에 -1를 해주며, -1된 숫자를 temp의 index로 사용하고, 그 index의 값에 data에서 세어준 원소를 넣어준다.

 

이미지 출처: https://www.oreilly.com/library/view/mastering-algorithms-with/1565924533/ch12s13.html

그림과 함께 설명하였지만.. 떨어지는 말솜씨로 최대한 내가 아는 알고리즘의 순서도를 적었다.

 

코드로 표현하자면

# 준비물
data = [0,4,1,3,1,2,4,1]
counts = [0]*(max(data)+1)
temp = [0]*len(data)

# 과정 1
for i in range(0,len(data)):
    counts[data[i]]+=1

# 과정 2
for i in range(1,len(counts)):
    counts[i] += counts[i-1]

# 과정 3,4
for i in range(len(temp)-1,-1,-1):
    counts[data[i]]-=1
    temp[counts[data[i]]] = data[i]
print(*temp)

그렇다면 출력값의 형태는

0 1 1 1 2 3 4 4

이 출력이 된다.