[알고리즘] 카운팅정렬 이해하기

1. 카운팅정렬이란

요소의 계수를 세고 정렬하는 알고리즘

리스트의 값의 범위가 크지 않을 때 효율적이다

 

지금까지 많은 알고리즘을 배우진 않았지만(버블 정렬, 카운팅 정렬, 선택정렬... 정도) 가장 이해가 힘들었던 정렬 중 하나로, 몇번이나 손코딩을 해야했다

 

2. 선택정렬 파이썬 코드

# 카운팅 정렬

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

sort_nums = [0] * len(nums)         #요소들을 정렬해줄 배열을 선언한다
big_num = -1                        #big_num은 요소들 중 가장 큰 값을 의미
for i in nums:
    if big_num < i:
        big_num = i

counts = [0] * (big_num + 1)        #가장 큰 값까지 카운팅 해줄 배열을 선언한다


for i in range(len(nums)):
    counts[nums[i]] += 1            #각 요소의 자리에 (해당 코드의 경우 9까지) 요소의 갯수를 더해준다
print(counts)                       #[0, 4, 1, 2, 1, 2, 2, 1, 1, 1]


for i in range(1, len(counts)):
    counts[i] += counts[i - 1]      # 배열에 누적값 표현
print(counts)                       #[0, 4, 5, 7, 8, 10, 12, 13, 14, 15]

for i in range(len(nums) - 1, -1, -1): # 뒤에서 부터 시행하는 이유는 안정정렬을 위해서
    n = nums[i]
    counts[n] -= 1
    idx = counts[n]
    sort_nums[idx] = n

print(sort_nums)

시간복잡도는 O(NM) N이 큰 경우 O(N), M이 큰 경우 O(M)이라고,,, 생각했는데 다른 블로그들을 보아 O(N) 인 것 같다