분류

  • 정렬 알고리즘

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
def counting_sort(max_n, arr):
	count = [0] * (max_n + 1)
	n_arr = []

	for x in arr:
		count[x] += 1

	for i in range(0, max_n + 1):
		if count[i] != 0:
			n_arr += [i] * count[i]

	return n_arr

설명

크기를 기준으로 숫자를 세어 정렬하는 알고리즘이다.

배열의 모든 원소가 양의 정수일때만 정렬 가능하다.

상당히 제한적이지만, 일반적으로 알려진 정렬 알고리즘의 한계 $O(nlogn)$를 극복할 수 있다.

복잡도

$O(n)$