Java 계수정렬 구현

1 개요[ | ]

Java 카운팅정렬 구현
자바 카운팅정렬 구현

2 트리맵 사용[ | ]

500,000회 수행 - CPU Time: 0.54 sec(s), Memory: 83568 kilobyte(s)

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 
    }
}

3 해시맵 사용[ | ]

500,000회 수행 - CPU Time: 2.56 sec(s), Memory: 168476 kilobyte(s)

import java.util.Collections;
import java.util.Arrays;
import java.util.HashMap;
public class MyClass {
    static void counting_sort(Integer a[]) {
        int min, max, i, j, c;
        min = Collections.min(Arrays.asList(a));
        max = Collections.max(Arrays.asList(a));
        HashMap<Integer,Integer> count = new HashMap();
        for(i=min; i<=max; i++) count.put(i,0);
        for(int x: a) count.put(x,count.get(x)+1);
        for(i=min, j=0; i<=max; i++) {
            c = count.get(i);
            while( c-- > 0 ) a[j++] = i;
        }
    }
    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 배열 사용[ | ]

음수 정렬 불가
500,000회 수행 - CPU Time: 0.30 sec(s), Memory: 86816 kilobyte(s)

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 같이 보기[ | ]