[알고리즘] 카운팅 정렬 (Counting sort) - 자바 Java

[ 개념 ] 

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적 알고리즘
- 정수나 정수로 표현할 수 있는 자료만 적용 가능 (각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스가 되는 카운트들의 배열을 사용하기 때문)
- 카운트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함

[ 과정 설명 (오름차순) ] 

1) Data 배열에서의 최댓값을 최대 인덱스로 갖는 counts 배열 생성 후, data에 각 인덱스에 해당하는 숫자가 몇 번 등장하는지 누적 카운팅

2) 뒤에서 부터 탐색하며, data 배열의 값에 해당하는 count 배열 인덱스로 가서 값을 -1 해준 뒤,
     result 배열에 해당 값의 인덱스로 가서 data 배열의 값 입력
     data 배열의 0번째 index에 도달할 때 까지 반복.

[ 코드 예시 (오름차순) - 자바 Java ]

import java.util.Arrays;

public class CountingSort {
  
  public static void main(String[] args) {
  
    int[] data = {3, 4, 1, 1, 2, 1, 4, 2};
    
    // data의 최댓값 찾아주기.
    int max = 0;
    for(int x : data) {
      max = Math.max(x, max);
    }
    
    // count 배열, result 값을 저장할 배열 생성.
    int[] count = new int[max+1];
    int[] result = new int[data.length];
    
    // data에 count 배열의 인덱스에 해당하는 숫자들이 몇 번 있는지 카운트.
    for(int x: data) {
      count[x]++;
    }
    
    // count 배열 누적합으로 변경.
    for(int i = 1; i <= max; i++) {
      count[i] += count[i-1];
    }
    
    // data 배열 뒤에서부터 돌면서 result에 정렬한 값 넣기.
    for(int i = data.length-1; i>=0 ; i--) {
      count[data[i]]--;
    result[count[data[i]]] = data[i];
    }
    
    System.out.println(Arrays.toString(result));
  }
  
}