수많은 정렬 알고리즘 중 시간복잡도가 𝚶(𝑛) 으로 엄청난 성능을 보여주는 알고리즘이다.
보통 빠르다는 정렬 알고리즘으로는 대표적으로 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort) 등이 있는데, 이들의 평균 시간복잡도는 𝚶(nlogn) 인 것에 비하면 엄청난 속도
기본적으로 정렬이라하면 데이터끼리 직접 비교하는 경우가 많다. 그렇기 때문에 데이터 직접 비교를 사용하는 정렬 알고리즘의 경우 𝚶(nlogn) 보다 작아질 수 없는 것이 한계다. 그렇다면 카운팅 정렬은 어떻게 이를 극복한 것일까?
그럼에도 왜 퀵 정렬같은 𝚶(nlogn) 의 정렬 알고리즘을 많이 사용하는 것일까?
💙 정렬 방법
카운팅 정렬은 데이터의 값이 몇 번 나왔는지를 세주는 것(counting)이다.
예시 배열
과정1
array를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index 로 하는 새로운 배열(counting)의 값을 1 증가시킨다.
array[0] = 7 이므로 counting[7] 값을 1 증가,
array[1] = 2 이므로 counting[2] 값을 1 증가,
…
array[11] = 1 이므로 counting[1] 값을 1 증가.
counting 배열의 의미는
0의 개수는 1개
1의 개수는 2개
2의 개수는 1개
…
이런식으로 counting 배열은 각 값의 개수가 담겨있는 배열이 된다.
과정2
counting 배열의 각 값을 누적합으로 변환시킨다.
과정2의 결과
정렬을 할 경우 counting 배열의 각 값은 (시작점 -1)을 알려준다는 것이다.
과정3
counting 배열의 각 값은 (시작점 -1)을 알려주고 있다. 즉, 해당 값에 대응되는 위치에 배정하면 된다는 의미다.
array[0] = 7 이고, counting[7] = 12 이다. 여기서 counting[7] 의 값에 1을 빼준 뒤 해당 값이 새로운 배열의 인덱스 11에 위치하게 된다.
array[1] = 2 이고, counting[2] = 4 이다. 여기서 counting[2]의 값에 1을 빼준 뒤 해당 값이 새로운 배열의 인덱스 3에 위치하게 된다.
즉, counting[n] 과 counting[n-1] 을 합한 값을 counting[n] 에 대입한 이유는 몇 번째인지 자리 배치를 하기 위해서다.
이런 식으로 배열 전체를 돌면 되는데 안정적으로 정렬하기 위해서는 array의 마지막 index 부터 순회하는 것이 좋다.
...
이 과정 자체가 두 수를 비교하는 과정이 없기 때문에 빠른 배치가 가능하다. 하지만 새로운 배열(counting[]) 을 선언해줘야한다. 배열을 크기에 따라 메모리가 낭비된다.
즉, Counting Sort가 효율적인 상황에서 쓰려면 수열의 길이보다 수의 범위가 극단적으로 크면 메모리가 엄청 낭비 될 수 있다는 것. 그렇기 때문에 각기 상황에 맞게 정렬 알고리즘을 써야하는데, 퀵 정렬이나 병합정렬 등이 선호되는 이유도 이에 있다.
Quick 정렬의 경우 시간복잡도 평균값이 𝚶(nlogn) 으로 빠른편이면서 배열도 하나만 사용하기 때문에 공간복잡도는 𝚶(𝑛) 으로 시간과 메모리 둘 다 효율적이라는 점이다.
💙 구현
🤍회고
백준 단계별 문제를 풀던 중 정렬 알고리즘 단계에 도달하게 되었다. 처음에는 단순히 최솟값과 최댓값을 찾아 정렬하는 방식으로 접근했지만, 과연 이것이 최선의 방법일까 하는 의문이 들었다. 그래서 다른 사람들의 풀이를 찾아보며 다양한 정렬 알고리즘이 존재한다는 사실을 알게 되었다.
그중 한 블로그 글을 참고해 카운팅 정렬에 대해 공부했는데, 처음에는 이해가 쉽지 않았다. 여러 번 글을 읽고, 코드를 디버깅하며, 손으로 직접 과정을 적어가며 반복한 끝에 비로소 개념을 이해할 수 있었다. 그렇게 어렵게 이해하게 된 정렬 알고리즘이라 더욱 기억에 남는다.
앞으로는 하루에 하나씩 해당 블로그를 참고해 정렬 알고리즘을 꾸준히 공부하며 완전히 익혀나갈 계획이다.
출처 및 참고 블로그 : https://st-lab.tistory.com/104
