카운팅 정렬(counting sort)이란?

파이썬을 사용할 때

데이터를 정렬할 일이 있다면

간단하게 .sort() or sorted()를

사용하면 빠르게 문제를 해결할 수 있다.

 

하지만

우리는 내장 함수 사용 없이

데이터를 정렬할 수도 있는데

그 방법 중 하나가 바로

카운팅 정렬이다.

 

오늘은 카운팅 정렬에 대해 알아보려 한다.

 

카운팅 정렬

 

카운팅 정렬은

비교 없이 값을 순서대로

정리하는 방법으로

 

각 값과 인덱스를 활용하여

정렬을 하는 방법이다.

 

1. lst 생성 및 counting

 

우선 정렬하고자 하는 값을 리스트로 생성한 후

최댓값을 구한다.

 

그리고 그 값을 카운팅하여

저장할 새로운 리스트를 만들기 위하여

가장 큰 값을 구한 후

[0] * (가장 큰 값 + 1)

라는 리스트(couning_lst)를 만든다.

(인덱스는 0부터 시작하기 때문)

 

이제 각각의 값을

i라고 한다면

새로운 리스트의 인덱스 위치 i에

그 값들을 수를 저장한다.

 

아래는 이해를 돕기 위한

이미지이다.

본인은 for문을 통해

기존의 리스트를 돌며

인덱스 위치 i에 +1을 해주는 방식을 사용했다.

 

코드는 아래와 같다.

 

lst = [4, 1, 5, 2, 1, 4, 3, 0, 1, 3]

# max값 = 5

counting_lst = [0]*6

for i in lst:
    counting_lst[i] += 1

    
# print(counting_lst) : [1, 3, 1, 2, 2, 1]

 

 

2. 누적 값과 정렬

 

이렇게 값을 구했다면

아래와 같은 방식으로

 

새롭게 생성된(counting_lst)의

누적 값을 구한다.

 

코드는 아래와 같다.

for num in range(1, len(counting_lst)):
    counting_lst[num] += counting_lst[num-1]

# print(counting_lst) [1, 4, 5, 7, 9, 10]

 

마지막으로

정렬된 결괏값을 출력할 리스트를

만들어주고 위의 값을 사용해

정렬하고자 하는 기존의 리스트를

거꾸로 순회하며

값을 저장한다.

(이는 같은 값이더라도

순서가 뒤바뀌지 않는

완전 정렬을 가능하게 한다.)

이와 같은 경우에서는

0은 첫 번째 칸에

1은 두 번째부터 네 번째 칸에

2는 다섯 번째 칸에

3은 여섯, 일곱 번째 칸에

4는 여덟, 아홉 번째 칸에

5는 마지막 열 번째 칸에 위치한다는 것이다.

 

여기에서 주의할 점은

1) 누적된 값의 -1 위치에 값이 존재한다는 것

(칸은 1부터 시작이지만 인덱스는 0부터 시작)

2) 사용한 누적 값은 -1씩 해준다는 것

이다.

 

이를 코드로 표현하면 다음과 같다.

for num in range(len(lst)-1, -1, -1):
    result[counting_lst[lst[num]]-1] += lst[num]
    counting_lst[lst[num]] -= 1

# print(result): [0, 1, 1, 1, 2, 3, 3, 4, 4, 5]

 

마무리

 

카운팅 정렬은

정수나 정수의 값만

존재하는 리스트에서 밖에

사용하지 못하며

 

또한, 각각의 값들의 차이가

클 때는 오히려

낭비를 불러일으킬 수 있다.

 

카운팅 정렬에 대해 배우며

상황에 맞는 방법이 다르다는 것을

알 수 있었고,

 

또한 인덱스를 이해하고 활용해볼 수 있는

좋은 기회였다.

 

*잘못된 부분이 있다면 댓글 부탁드리겠습니다!