[Java] 카운팅 정렬 (Counting Sort)

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

백준 10989번 수 정렬하기3 문제를 Collections.sort()로 오름차순 정렬했더니 아래와 같은 메모리 초과 오류가 떴다.

구글링을 통해 알아보았더니, Collections.sort()나 Arrays.sort()같은 메소드는 평균 시간복잡도가 𝚶(nlogn) 인 반면에

Counting sort는 평균 시간복잡도가 𝚶(𝑛) 인 성능을 보여주는 알고리즘인 것을 알게 되었다.

Arrays.sort()는 평균: 𝚶(nlogn) / 최악: 𝚶(n^2)
Collections.sort()는 평균, 최악 : 𝚶(nlogn) 의 시간복잡도를 가진다.

 

 

단, 카운팅 정렬은 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점이다.(배열안의 가장 큰 원소가 엄청나게 큰 숫자가 아니라면 사용하자!) 

---

간단하게 카운팅 정렬은, 데이터의 값이 몇 번 나왔는지를 세어주고, 해당 값을 인덱스로 하는 새로운 배열(counting)의 값을 1 증가시킨다. 그림으로 예를 들어보겠다.

출처: https://st-lab.tistory.com/104

array[0] = 7이므로 counting[7] 값을 1 증가,

array[1] = 2 이므로 counting[2] 값을 1 증가,

...

array[11] = 1 이므로 count[1] 값을 1 증가.

이 과정을 마치면 위 그림과 같은 counting 배열이 완성이된다.

 

원래라면, counting 배열의 각 값을 누적합으로 변환시켜줘야 하지만, 10989번 백준문제와 같이 수의 범위를 알고 있고 입출력만 하는 것이라면 아래와 같이, 누적 합 부분을 skip하고 count[i]값이 0이 될 때까지 인덱스를 출력해주면 된다.

for(int i = 1; i < 10001; i++) {
    while(cnt[i] > 0) {
        System.out.println(i);
        cnt[i]--;
    }
}