계수 정렬(Counting Sort) 알고리즘이란?

계수 정열 알고리즘은 기존 비교 알고리즘과 다르게 데이터 값을 서로 비교하지 않고,
원본 데이터의 원소 개수를 세어 정렬하는 알고리즘입니다

기본 원리

먼저 원본 배열의 원소 중 최댓값을 찾습니다
그리고 최댓값의 크기만큼 카운팅 배열을 새롭게 만듭니다

원본 배열을 탐색하며, 각 원소의 개수를 카운팅 배열에 저장합니다
누적합 방식을 이용해 카운팅 배열에 이전까지의 원소 개수를 저장합니다

이제 원본 배열의 뒤에서부터 데이터를 탐색하며 누적합을 기준으로 각 숫자를 정렬된 위치에 배치합니다

시간복잡도

계수 정렬 알고리즘의 시간복잡도에 대해 알아보겠습니다

• N: 데이터의 개수
• K: 데이터 값의 범위
  계수 정렬 알고리즘의 시간복잡도는 O(n+k)로 값의 범위와 데이터 개수에 의존합니다
  데이터 개수나 값의 범위가 작을 수록 매우 빠른 성능을 보장합니다

그리고 이 시간복잡도는 평균,최악,최선의 상황 모두에서 동일한 성능을 보장합니다

장점

• 계수 정렬은 기수 정렬처럼 비교 기반 정렬보다 빠를 수 있으며,
  특히 정수형 데이터에서 값의 범위가 작을 때 효율적입니다
• 데이터 범위가 작다면 빠른 성능을 보장할 수 있습니다
• 마지막에 정렬할 때, 뒤에서부터 탐색하기 때문에 안정정렬을 보장합니다

단점

• 데이터 값의 범위가 클 수록 추가 메모리 사용이 많아 비효율적입니다
• 음수값을 처리할 때는 별도 변환과정이 필요하고 실수나 문자열은 정렬이 불가능합니다

결론

계수정렬 알고리즘은 비교기반 알고리즘과 다르게, 원본배열의 원소 개수를 바탕으로 정렬하는 알고리즘입니다
원소 개수나 값이 작을 수록 좋은 성능을 보이나, 한가지라도 큰 경우 메모리 사용량이 커져 비효율적입니다