[Computer Science] 카운팅 정렬

Counting Sort

• 계수정렬은 O(n)의 시간복잡도를 갖는다
• 일반적 상황에서 가장 빠른 정렬 알고리즘인 Quick Sort는 O(nlogn)을 가진다
• 그렇다면 대부분의 정렬이 필요한 상황에서 카운팅정렬을 사용하지 않고 퀵정렬을 사용할까??

정렬과정

1. 첫번째로 각 숫자가 몇 번 등장하는지 세어준다.

1. 등장 횟수의 누적합을 구해준다

  여기서 누적합의 의미를 알아보자

숫자 0은 0번째 index에서 1번째 사이에 위치한다 ( 0 )

숫자 1은 1번째 index에서 4번째 사이에 위치한다 (1 , 2 , 3)

숫자 2는 4번째 index에서 4번째 사이에 위치한다 ( X )

숫자 3은 4번째 index에서 6번째 사이에 위치한다 (4, 5)

1. 누적합을 이용해 정렬 (안정정렬을 만들기 위해 a의 맨 뒤에서부터 정렬을 시작한다)

• 맨 뒤의숫자인 1이 가지고 있는 누적합(4)를 찾아간다.

 

 

• 누적합을 한개 줄인다 (3) → 감소한 누적합 자리에 1을 삽입

• 맨 뒤의숫자에서 한칸앞인 3이 가지고 있는 누적합(5)를 찾아간다.
• 누적합을 한개 줄인다 (4) → 감소한 누적합 자리에 3을 삽입

정리

1. Counting Sort(계수정렬)는 안정정렬이다.
2. 데이터의 범위는 상대적으로 좁은데 비해 데이터의 갯수가 많은 경우 사용하기 적합하다
3. 데이터의 범위가 상대적으로 넓은데 비해 데이터의 갯수가 적다면 매우 비효율적이다.
4. -예를 들어 80, 50 , 30, 1000 이라는 배열이 있다면 배열을 1~1000까지 잡아야 한다.
5. 시간복잡도는 모든 상황에서 O(N)이다.