계수정렬 구현

Jmnote (토론 | 기여)님의 2018년 7월 15일 (일) 23:25 판 (→‎Java)

1 C

#include <stdio.h>
#include <string.h>
void count_sort(int arr[], int size) {
    int i, max=arr[0];
    for(i=0; i<size; i++) if( arr[i]>max ) max=arr[i];
	int output[size], count[max+1];
	memset(count, 0, sizeof(count));
	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(arr[0]);
	count_sort(arr, size);
	for(int i=0; i<size; i++) printf("%d ",arr[i]);
}

2 Java

import java.util.Arrays;
public class MyClass {
	private static void count_sort(int arr[]) {
		int i, size=arr.length, max=arr[0];
		for(int e:arr) if(max<e)max=e;
		int output[] = new int[size];
		int count[] = new int[max+1];
		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];
	}
	public static void main(String args[]) {
		int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
		count_sort(arr);
		System.out.println( Arrays.toString(arr) );
		// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
	}
}

3 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]

4 같이 보기

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}