계수 정렬 (Count Sort)
기본 개념
•
계수 정렬은 비교연산을 사용하지 않고, 이름 그대로 배열 내에 특정 값이 몇 번 등장하는지를 통해 정렬을 수행하는 알고리즘
원리
1.
입력 받은 배열 A의 요소 값들의 등장 횟수를 저장할 배열 B와 최종적으로 정렬된 값들을 담을 배열 C를 준비
2.
입력 받은 배열에서 값을 하나씩 꺼내, 해당 값을 B의 인덱스로 사용해 B의 요소 값 하나 증가
•
B[A[i]]++
3.
배열 B가 완성되면, B의 각 요소들을 누적 합으로 갱신
•
B[i] = B[i] + B[i-1]
4.
A의 가장 뒤에서부터 값을 하나씩 꺼내 해당 값을 B의 인덱스로 사용하고 참조된 B의 값 하나를 감소한다.
•
B[A[i]]--
5.
감소된 B의 값을 배열 C의 인덱스로 사용해 A에서 꺼낸 값을 넣는다.
•
C[B[A[i]]] = A[i]
6.
A의 모든 요소에 대해, 4, 5번 과정 반복
예시
•
배열 A를 입력 받고, 배열 B와 C를 준비
•
이때 B의 크기는 A의 최대값 +1 의 크기이다 → 인덱스로 쓰기 때문에
•
A를 순회하며 등장하는 값들의 등장 횟수를 배열 B에 저장한다.
•
1차로 완성된 배열 B를 누적합으로 업데이트 한다.
•
배열 A의 맨 뒤에서부터 값을 하나씩 꺼내서 B의 인덱스로 접근 후 하나 감소
◦
배열 B에서 6번 인덱스의 값이 6이다. 이는 배열 A에 6보다 같거나 작은 수가 6개 존재한다는 의미
•
해당 값을 C의 인덱스로 접근 후 꺼낸 값을 저장
분석
장점
•
비교 연산을 하지 않기 때문에 빠르다
단점
•
카운팅을 위한 배열의 길이가 최대값에 의해 결정된다
◦
만약 (1, 100000) 두 개의 값만 가지더라도 카운팅 배열의 크기는 100001
•
시간 복잡도는 O(N) 이다.
◦
데이터의 수보다 배열의 크기가 터무니없이 커지면 비효율적