계수정렬 구현

1 C

#include <stdio.h>
#define MAX 100
void count_sort(int arr[], int size) {
    int i, output[size], count[MAX] = {0};
    for(i=0; i<size; i++) count[arr[i]]++;
    for(i=1; i<=MAX; i++) count[i] += count[i-1];
    for(i=0; i<size; i++) {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    for(i=0; i<size; i++) arr[i] = output[i];
}
int main() {
    int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
    int size = sizeof(arr)/sizeof(int);
    count_sort(arr, size);
    for(int i=0; i<size; i++) printf("%d ",arr[i]);
}

2 Python

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

3 같이 보기