계수정렬 구현

계수정렬 구현
카운팅정렬 구현

1 C[ | ]

 
#include <stdio.h>
#include <string.h>
void counting_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(int);
	counting_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++[ | ]

#include <iostream>
void counting_sort(int a[], int size) {
	int i, max=a[0];
	for(i=0; i<size; i++) if( a[i]>max ) max=a[i];
	int output[size], count[max+1] = {0};
	for(i=0; i<size; i++) count[a[i]]++;
	for(i=1; i<=max; i++) count[i] += count[i-1];
	for(i=0; i<size; i++) {
		output[count[a[i]]-1] = a[i];
		count[a[i]]--;
	}
	for(i=0; i<size; i++) a[i] = output[i];
}
int main() {
	int arr[] = {9,1,22,4,0,1,22,100,10};
	counting_sort(arr, sizeof(arr)/sizeof(int));
	for(int x: arr) std::cout << x << " ";
	// 0 1 1 4 9 10 22 22 100 
}

3 C#[ | ]

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

4 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 
    }
}
배열 사용, 음수 정렬 불가
public class MyClass {
	static void counting_sort(int a[]) {
		int i, size=a.length, max=a[0];
		for(int x: a) if(max<x)max=x;
		int output[] = new int[size];
		int count[] = new int[max+1];
		for(i=0; i<size; i++) count[a[i]]++;
		for(i=1; i<=max; i++) count[i] += count[i-1];
		for(i=0; i<size; i++) {
			output[count[a[i]]-1] = a[i];
			count[a[i]]--;
		}
		for(i=0; i<size; i++) a[i] = output[i];
	}
	public static void main(String args[]) {
		int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
		counting_sort(arr);
		for(int x:arr) System.out.format("%d ",x); 
		// 0 1 2 3 4 5 6 7 8 9 10 100 
	}
}

5 PHP[ | ]

function counting_sort(&$a) {
    $count=[];
    foreach($a as $x) {
        if(!array_key_exists($x,$count)) $count[$x]=1;
        else $count[$x]++;
    }
    ksort($count);
    $pos=0;
    foreach($count as $x => $repeat) {
        while( $repeat-- > 0 ) $a[$pos++]=$x;
    }
}
$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

6 Python[ | ]

def counting_sort(a):
	count={}
	for x in a: count[x]=count.get(x,0)+1
	pos=0
	for x,repeat in sorted(count.items()):
	    a[pos:pos+repeat] = [x]*repeat
	    pos += repeat
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]

7 Ruby[ | ]

def counting_sort(a)
    count={}
    for x in a
        if not count.key?(x) then count[x]=1
        else count[x]+=1 end
    end
    pos = 0
    for x,repeat in count.sort_by {|k,v| k}
        a[pos,repeat] = Array.new(repeat,x)
        pos += repeat
    end
end
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]

8 같이 보기[ | ]

9 참고[ | ]

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