O(n) - counting sort (카운팅 정렬) 알고리즘

카운팅 정렬은 O(n)의 파워를 가지는 알고리즘이다.

분명 시간복잡도만 보았을 때는 '이게 제일 효율적이지 않나'라고 생각할 수 있지만, 자주 쓰이지 않는 이유가 있다.

 

카운팅 정렬의 알고리즘을 간단하게 본다면,

기존 배열의 값에 해당하는 원소들에 대해 인덱스를 갖는 새로운 배열을 만들어 정렬하는 방식이다.

 

만약 기존 배열의 길이가 적지만 엄청나게 큰 수가 적혀있으면 그 큰 수만큼의 배열을 할당받을 메모리가 필요한 셈이다.

그러므로 때에 따라 사용할 수 있는 조건부 알고리즘인 셈이다.

 

카운팅 알고리즘은 다음과 같다.

1. 기존 배열의 가장 큰 값의 원소를 길이로 하는 새로운 배열 1을 받고, 그 원소에 해당하는 인덱스에 값을 1씩 더해준다.

2. 새로운 배열 1에 대해 누적합을 구해준다.

3. 정렬된 값을 넣기 위해 기존 배열과 길이가 같은 새로운 배열 2를 만들고, 누적합에 대해 새로운 배열 1의 뒤부터 값을 넣어준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NSort_countingSort {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] array = new int[n];

        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(br.readLine());
        }
        //counting sort


        //======================== maximum ========================
        int max = 0;
        for(int maximum : array){
            if(max < maximum){
                max = maximum;
            }
        }


        int[] counting = new int[max + 1];

        for(int i = 0; i < array.length; i++){
            counting[array[i]]++;
        }

        //누적합
        for(int i = 1; i < counting.length; i++){
            counting[i] += counting[i - 1];
        }

        int[] result = new int[n];

        for(int i = result.length - 1; i >= 0; i--){
            int value = array[i];
            counting[value]--;
            result[counting[value]] = value;

        }


        StringBuilder sb = new StringBuilder();

        for(int rst : result){
            sb.append(rst).append('\n');
        }

        System.out.println(sb);





    }
}