[알고리즘 정렬] 계수 정렬(Counting Sort)

  계수 정렬(Counting Sort)이란 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식입니다. 카운팅을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(n + k)입니다. k는 정렬 대상 데이터 중 최대 값을 의미합니다.

  카운팅 테이블은 Array 자료구조로 되어 있습니다.

 

정렬되지 않은 데이터

10

32

10

27

32

17

99

56

↓

2

1

1

2

1

1

[0]

[…]

[10]

[…]

[17]

[…]

[27]

[…]

[32]

[…]

[56]

[…]

[99]

↓

정렬이 끝난 데이터

10

10

17

27

32

32

56

99

 

  계수 정렬 구현 코드

import java.util.Arrays;

public class Main {
    public static void countingSort(int[] array) {
        int max = Arrays.stream(array).max().getAsInt();
        int[] countArray = new int[max + 1];

        for (int i = 0; i < array.length; i++) {
            countArray[array[i]]++;
        }
        int index = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i] > 0) {
                array[index++] = i;
                countArray[i] -= 1;
            }
        }
    }
}

  매개 변수로 배열 array를 받는 countingSort 메소드를 생성합니다.  

  변수 max를 생성합니다. stream을 이용하여 array의 원소 중 가장 큰 값을 구합니다. for문을 이용하는 등 다양한 방법으로도 구현해도 무방합니다.

  countArray를 생성합니다. 크기는 max에서 1을 더한 값입니다. 이 배열의 크기는 정렬을 원하는 배열에서의 가장 큰 원소만큼이 되는 것입니다.

  for문이 array의 길이만큼 순회합니다.

  countArray의 array의 i 번째 원소 위치에 해당하는 값의 인덱스가 증가합니다.

  변수 index를 생성합니다.

  for문이 countArray의 길이만큼 순회합니다.

  while문은 countArray의 i 번째 원소가 0보다 큰 동안 반복합니다.

  array의 index 번째 원소가 1씩 증가하면서 각 인덱스에 i를 할당합니다. array에 값을 추가했으므로 countArray의 i 번째 원소에서 1을 뺍니다. 만약 남은 수가 0보다 크다면 다시 array에 i를 추가하고 countArray의 원소가 1 감소할 것입니다.