선형시간 정렬

계수정렬(Counting Sort)

 

1. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다.
  가장 작은 원소와 가장 큰 원소를 구한다.
  가장 작은 원소부터 가장 큰 원소까지의 실제 숫자를 key(index)로 가지는 배열을 만든다.
  배열에서 실제 숫자의 갯수를 센다.

2. 갯수를 하나씩 줄여가면서 해당 위치에 요소를 넣어준다.

 

의사코드

 

수행시간

O(N+K)

 

 * k는 입력되는 정수의 범위이다. 

 

계수정렬이 유리한 경우

동일한 숫자가 반복되고, MIN과 MAX 값의 범위가 적을 때

 

JAVA 구현

package algorithm;

import java.util.Arrays;

public class CountingSort {
	
	public int[] countingSort(int[] arr, int min, int max) {
		
		int[] c = new int[max-min+1];
		int[] out = new int[arr.length];
		
		for(int a : arr) {
			c[a-min]++;
		}
		
		for(int i = 1; i < c.length ; i++) {
			c[i] += c[i-1];
		}
		
		for(int i = arr.length-1; i>=0; i--) {
			
			out[c[arr[i]-min]-1] = arr[i];
			c[arr[i]-min]--;
		}
		
		return out;
	}

	


	public static void main(String[] args) {
		int[] arr = new int[] {3, 5, 1, 6, 9, 2, 4};
		
		CountingSort f= new CountingSort();
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int a : arr) {
			if(min>a) min = a;
			if(max<a) max = a;
		}
		
		int[] out = f.countingSort(arr, min,max);
		
		System.out.println(Arrays.toString(out));
		
	}
}