계수정렬 구현

1 C

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]);
	// 0 1 2 3 4 5 6 7 8 9 10 100 
}

2 C#

C샵 카운팅정렬 구현 문서를 참고하십시오.

using System;
using System.Linq;
class Program {
	static void count_sort(int []arr) {
		int i, size = arr.Length, max = arr.Max();
		int[] output = new int[size];
		int[] count = new int[max+1];
		for(i=0; i<max; i++) count[i] = 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];
	}
	static void Main() {
		int[] arr = {3,4,2,1,7,5,8,9,0,6,100,10};
		count_sort(arr);
		foreach(int i in arr) Console.Write(i+" ");
		// 0 1 2 3 4 5 6 7 8 9 10 100 
	}
}

3 Java

Java 카운팅정렬 구현 문서를 참고하십시오.

import java.util.Map;
import java.util.TreeMap;
public class MyClass {
    static void counting_sort(Integer a[]) {
        Map<Integer,Integer> count = new TreeMap();
        for(int x: a) {
            if( !count.containsKey(x) ) count.put(x,1);
            else count.put(x,count.get(x)+1);
        }
        int k, v, pos=0;
        for (Map.Entry<Integer,Integer> entry: count.entrySet()) {
            k = entry.getKey();
            v = entry.getValue();
            while( v-- > 0 ) a[pos++] = k;
        }
    }
    public static void main(String args[]) {
    	Integer arr[] = {9,1,22,4,0,-1,1,22,100,10};
    	counting_sort(arr);
    	for(int x:arr) System.out.format("%d ",x); 
    	// -1 0 1 1 4 9 10 22 22 100 
    }
}

4 PHP

PHP 카운팅정렬 구현 문서를 참고하십시오.

<?php
function counting_sort(&$a) {
    $min = min($a);
    $max = max($a);
    $count = [];
    for($i=$min; $i<=$max; $i++) $count[$i]=0;
    foreach($a as $x) $count[$x]++;
    for($i=$min, $j=0; $i<=$max; $i++) {
        while( $count[$i]-- > 0 ) $a[$j++] = $i;
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
counting_sort( $arr );
echo implode(' ', $arr);
# -1 0 1 1 4 9 10 22 22 100

5 Python

Python 카운팅정렬 구현 문서를 참고하십시오.

def counting_sort(a):
	count = {}
	for x in a: count[x]=count.get(x,0)+1
	i = 0
	for x, c in sorted(count.items()):
	    a[i:i+c] = [x]*c
	    i += c
arr = [9,1,22,4,0,-1,1,22,100,10]
counting_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

6 같이 보기

• 계수정렬
• 정렬 구현
• 기수정렬 구현

7 참고

• https://www.geeksforgeeks.org/counting-sort/