카운팅 정렬 (Counting Sort)

카운팅 정렬

- 입력되는 값을 값이자 인덱스로 보고 새로운 카운팅 배열에 추가를 하며 개수를 기반으로 정렬하는 알고리즘

- 비교를 하지 않기 때문에 숫자의 범위가 작을때 빠르고 효율적으로 정렬할 수 있는 알고리즘

- 숫자의 개수는 적은데 값의 범위가 커진다면 비효율적인 알고리즘

- 카운팅 배열이라는 새로운 배열과 출력값을 저장할 새로운 배열 2개가 더 생성되기 때문에 다른 정렬 알고리즘에 비해서 메모리를 더욱 많이 사용함

 

정렬 알고리즘

 

Step 1. Counting Array

출처 : https://st-lab.tistory.com/104

Step 2. Counting Array Summing

출처 : https://st-lab.tistory.com/104

Step 3. Sorting

출처 : https://st-lab.tistory.com/104

1. 값을 받은 다음 max + 1 의 길이에 해당하는 counting 배열을 만듦

2. counting 배열에는 기존 배열의 값을 인덱스로 보고 +1 씩 더해줌

3. counting 배열을 순차적으로 더해 줌. ex( 1 0 2 0 1 -> 1 1 3 3 4 )

4. 정렬을 한 값을 저장하기 위한 arr 배열의 길이와 같은 arr2 배열을 하나 생성

5. counting[arr]의 값을 -1 하면서 arr2[coungting[arr]] 위치에 arr 값을 넣어주면서 정렬

 

 

JAVA Code

import java.io.*;

public class CountingSort {
    public static int[] countingSort(int arr[], int max) {
//        OptionalInt max = IntStream.range(0, arr.length).map(i -> arr[i]).max();
//        int[] countArr = new int[max.getAsInt()+1];
        int[] countArr = new int[max + 1];

        // Step 1. Make Counting Array
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }

        // Step 2. Counting Array Summing
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i-1];
        }

        // Step 3. Sorting
        int arr2[] = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[--countArr[arr[i]]] = arr[i];
        }

        return arr2;
    }

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

        int arr[] = new int[_loop];
        int max = 0;
        for (int i = 0; i < _loop; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        arr = countingSort(arr, max);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        try {
            for (int i = 0; i < arr.length; i++) {
                bw.write(arr[i]+"\n");
            }
        } catch (IOException e) {
        } finally {
            bw.close();
        }
    }
}