countingSort

countingSort.java

void countingSort(int[] arr) {
  int n = arr.length;

  int output[] = new int[n]; // 결과를 저장할 임시 배열

  int count[] = new int[256]; // arr 에 정수 입력값중에 255 를 넘어가는 건 정렬되지 않습니다...

  for (int i = 0; i < n; ++i)
    ++count[arr[i]]; // 계수 를 측정합니다. 

  for (int i = 1; i < 256; ++i) // 앞의 원소를 더하여 누적시킵니다. 
    count[i] += count[i - 1];

  for (int i = n - 1; i >=0; i--) { 
    // 같은 키의 순서를 유지하기 위해 n-1에서 0으로 내려가면서 역순으로 실행하였습니다...
    output[count[arr[i]] - 1] = arr[i]; // output 배열에 실제 정렬을 수행합니다. 
    --count[arr[i]]; // 정렬된 원소는 counting 계수를 1 감소시킵니다.
  }

  for (int i = 0; i < n; ++i)
    arr[i] = output[i]; // 원본 배열에 결과를 저장
}