계수정렬(Counting Sort)

각 숫자가 몇번 나오는지 count를 한 후 앞 순서대로 차례대로 다시 내보내 정렬 시키는 정렬 알고리즘

0. [3,4,0,1,2,4,2,4], [개수를 count한 후 저장할 공간] 

1. 개수를 저장할 공간을 0으로 초기화 시켜준다. 배열의 크기는 데이터 배열의 최대값
    [3,4,0,1,2,4,2,4], [0,0,0,0,0] // 
2. 처음부터 개수를 세어 저장합니다. 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개
    [3,4,0,1,2,4,2,4], [1,1,2,1,3]
3. 개수를 저장한 것을 누적합시킨다.
    [3,4,0,1,2,4,2,4], [1,2,4,5,8]
4. 누적합을 바탕으로 숫자를 결과에 넣어줌. 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어준다.
    결과 : [0,1,2,2,3,4,4,4]

 

시간복잡도

k = 원소의 최대값

기존 배열 n을 돌고 count배열의 크기 k만큼 돌게 되므로 O(n+k)

원소의 최대값 중 하나가 매우 큰 수가 된다면 시간복잡도가 매우 커질 수 있다.

 

공간복잡도

k = 원소의 최대값

기존 배열 n에 count배열의 크기 k가 추가되므로 O(n+k)

원소의 최대값이 유독 큰 값이 하나라도 존재해도 크 크기만큼 배열의 크기를 잡아야 하므로 메모리 낭비가 심한 정렬 방식

 

Code

class Main {
  // 1,2,3,7,7,7,8,9,10,10
    public static void main(String[] args) {
      int[] data = {7,7,3,2,1,8,9,10,10,7};
      int[] sortedArr = countingSort(data);
      for (int num : sortedArr) {
        System.out.println(num);
      }

    }

    public static int[] countingSort(int[] data) {
      int maxNumber = getMaxNumber(data);
      int[] sortedArr = new int[data.length];
      // counting 배열 만들기
      int[] countArr = new int[maxNumber+1];
      for (int number : data) {
        countArr[number]++;
      }

      // counting 배열 prefix-sum
      for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i-1];
      }

      for (int i = data.length-1; i > -1; i--) {
        sortedArr[countArr[data[i]]-1] = data[i];
        countArr[data[i]]--;
      }

      return sortedArr;
    }

    private static int getMaxNumber(int[] data) {
      int maxNumber = data[0];
      for (int number : data) {
        if (number > maxNumber) {
          maxNumber = number;
        }
      }
      return maxNumber;
    }
}

/*
결과
1 2 3 7 7 7 8 9 10 10
*/