Java 계수정렬 구현

개요

Java 카운팅정렬 구현

자바 카운팅정렬 구현

트리맵 사용

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

해시맵 사용

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

배열 사용

• 음수 정렬 불가
• 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 
	}
}

같이 보기

• 카운팅정렬 구현
• 카운팅정렬