계수 정렬 (Counting Sort)

정의

---

• 데이터의 값이 몇번 나왔는지 count한다

정렬 방법

---

1. 각 값의 개수가 담겨있는 배열
2. counting 배열 값들의 누적합을 설정해줌 : counting배열의 각 값은 (시작점 - 1)을 알려준다

코드

---

재귀 (Top-Down 형식)

public class CountingSort {
	public static void main(String[] args) {
    	int[] array = new int[100];
        int[] counting = new int[31];
        int[] result = new int[100];
        
        for(int i = 0; i < array.length; i++) {
        	array[i] = (int)(Math.random()*31);
        }
        
        //Counting Sort
        for(int i = 0; i < array.length; i++){
        	//array의 value값을 index로 하는 counting배열 값 1 증가
        	counting[array[i]]++;
        }
        //누적합 계산
        for(int i = 1; i < counting.length; i++) {
        	counting[i] += counting[i - 1];
        }
        //i번째 원소를 인덱스로 하는 counting배열을 1감소시킨 뒤
        //counting배열의 값을 인덱스로 하여 result에 value값을 저장한다.
        for(int i = array.length - 1; i >= 0; i--) {
        	int value = array[i];
            counting[value]--;
            result[counting[value]] = value;
        }
}

장점 & 단점

---

-장점

• O(N)의 시간복잡도로 엄청 빠르다

-단점

• 메모리 낭비

시간복잡도

---

O(N)