- 계수정렬 구현
- 카운팅정렬 구현
1 C[ | ]

C
Copy
#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
}
Loading
2 C++[ | ]

C++
Copy
#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
}
Loading
3 C#[ | ]

C#
Copy
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
}
}
Loading
4 Java[ | ]

트리맵 사용
Java
Copy
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
}
}
Loading
배열 사용, 음수 정렬 불가
Java
Copy
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
}
}
Loading
5 PHP[ | ]

PHP
Copy
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
Loading
6 Python[ | ]

Python
Copy
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]
Loading
7 Ruby[ | ]

Ruby
Copy
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]
Loading