계수 정렬 알고리즘이란?

오늘은 정렬 알고리즘 중 비교를 사용하지 않는 정렬 방법인 계수 정렬에 대해 소개하려고 한다

참고로 계수 정렬은 입력의 특정 범위가 있을 때 유용하게 사용할 수 있는 정렬 알고리즘이다

계수 정렬이란?

계수 정렬은 주어진 입력 배열에서 각 숫자의 발생 횟수를 계산하고 이 정보를 사용하여 배열을 다시 정렬하는 방법으로

이 알고리즘의 핵심 아이디어는 숫자의 발생 횟수와 숫자의 상대적인 순서를 사용하여 정렬하는 것이다

계수 정렬의 작동 방식

글로만 보면 어렵게 느껴질 수 있으므로 예시를 통해 설명해보자.

정렬해야 하는 리스트:

[4, 2, 2, 8, 3, 3, 1]

먼저 주어진 리스트의 최대값과 최소값을 찾아 그 사이의 범위를 확인한다 여기서는 1에서 8까지이다

다음으로 해당 범위의 크기만큼의 계수 배열을 만든다

첫 단계에서는 각 숫자의 발생 횟수를 계수 배열에 기록한다

1: 1회, 2: 2회, 3: 2회, 4: 1회, 8: 1회

이제 계수 배열을 사용하여 원래 배열을 재구성한다

[1, 2, 2, 3, 3, 4, 8]

이와 같이 원 배열이 오름차순으로 정렬된다

계수 정렬의 장단점

마지막으로 계수 정렬 알고리즘에 장단점을 알아보자

장점:

1. 비교 기반 정렬 알고리즘의 제한된 O(n log n)보다 빠른 O(n + k)의 시간 복잡도를 가진다
2. 안정 정렬(Stable Sort)로 구현할 수 있다

단점:

1. 정수에만 사용할 수 있다
2. 입력 배열의 최대값과 최소값의 차이가 클 경우 메모리 사용량이 많아진다