[Algorithm] Counting Sort (계수정렬)

1. Counting Sort

 

계수 정렬은 배열의 원소의 개수를 세어 정렬하는 방식의 알고리즘이다. 특정 값을 가진 원소가 몇개인지를 세어 개수를 가지고 정렬을 진행하기 때문에 특정한 범위의 값들을 원소로 가질때 적합하다. 범위가 넓은 경우에는 원소들을 계수하기 위해 할당하는 배열의 크기가 커지는 문제가 발생한다.

 

 

2. Counting Sort 구현

 

배열의 원소들을 각각의 값에 따라 계수하기 위해서 원소들의 개수를 저장할 임시 배열을 할당한다. 이때 임시 배열의 크기는 배열에 저장된 값의 범위에서 가장 큰 값으로 한다.

 

임시 배열을 생성한 후에는 기존 배열을 처음부터 끝까지 탐색하면서 해당 원소의 값을 인덱스로 가지는 임시 배열의 원소의 값을 하나씩 더해준다. 기존 배열의 탐색이 끝난 뒤에는 임시 배열을 처음부터 끝까지 훓으면서 계수된 값만큼 결과 배열에 원소를 입력하는 방식으로 정렬한다.

 

import java.util.Arrays;

import Algorithm.Sorting.Sort;

public class CountingSort implements Sort {

    private int[] array;

    private int N;

    // N은 배열에 들어가는 원소의 값의 범위이다.
    public CountingSort(int[] array, int N) {
        this.array = Arrays.copyOf(array, array.length);
        this.N = N;
    }

    @Override
    public int[] sort() {
        // array에 저장된 원소들의 값을 계수한다.
        int[] countingArray = new int[N + 1];
        for(int num : array) {
            countingArray[num]++;
        }

        // 임시 배열에 계수된 만큼 원소들을 차례로 결과 배열에 입력한다.
        int index = 0;
        for(int i = 0; i < N + 1; i++) {
            while(0 < countingArray[i]--) {
                array[index++] = i;
            }
        }

        return array;
    }
    
}

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Sorting/CountingSort/CountingSort.java

 

3. Counting Sort 복잡도

 

[reference]

- https://en.wikipedia.org/wiki/Counting_sort

Counting sort - Wikipedia

- https://www.geeksforgeeks.org/counting-sort/

Counting Sort - GeeksforGeeks