Python 계수정렬 구현

1 개요

Python 카운팅정렬 구현

원본 미보존

def count_sort(arr):
	size = len(arr)
	mx = max(arr)
	output = [0]*size
	count = [0]*(mx+1)
	for i in range(size):
		count[i] += 1
	for i in range(mx):
		count[i] += count[i-1]
	for i in range(size):
		output[count[arr[i]]-1] = arr[i]
		count[arr[i]] -= 1
	for i in range(size):
		arr[i] = output[i]
arr = [3,4,2,1,7,5,8,9,0,6,100,10]
count_sort(arr)
print( arr )
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

원본 보존

def count_sort(arr):
	size = len(arr)
	mx = max(arr)
	output = [0]*size
	result = [0]*size
	count = [0]*(mx+1)
	for i in range(size):
		count[i] += 1
	for i in range(mx):
		count[i] += count[i-1]
	for i in range(size):
		output[count[arr[i]]-1] = arr[i]
		count[arr[i]] -= 1
	for i in range(size):
		result[i] = output[i]
	return result 
arr = [3,4,2,1,7,5,8,9,0,6,100,10]
sorted = count_sort(arr)
print( arr )
print( sorted )
# [3, 4, 2, 1, 7, 5, 8, 9, 0, 6, 100, 10]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

2 같이 보기