[알고리즘] 계수정렬

계수 정렬이란?

---

계수 정렬은 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘이다. 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬을 했는데, 계수 정렬에서는 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요가 없다.

계수 정렬의 큰 특징은 값 비교가 일어나지 않기 때문에 속도가 빠르다는 것이다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간이 필요하다. 그래서, 정렬해야 할 수의 범위가 작을 때에만 유리하다. 이 이유는 예를 보면서 설명하겠다.

EX) 0, 100, 2, 10, 10000 오름차순으로 정렬하기

예를 들어서 정렬해야 할 수가 0, 100, 2, 10, 10000이면 고작 5개의 수를 정렬하는데 0부터 10000까지의 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다.

계수 정렬 과정

---

1. 정렬하고자 하는 배열의 최댓값을 구한다
2. 최댓값 크기의 배열에 각 원소를 순회하며 해당 값이 몇 개 인지 저장한다
3. 저장된 데이터를 순서대로 출력한다
   이제 예시를 한번 살펴보도록 하겠다.

EX) 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1, 2, 3, 5 ,2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1 정렬하기

• 0. 초기 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  0	0	0	0	0

• 1. 1번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	0	0	0	0

• 2. 2번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	0	1	0	0

• 3. 3번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	1	1	0	0

• 4. 4번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	1	1	1	0

• 5. 5번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	1	2	1	0

• 6. 6번째 상태

  1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

  크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
  1	2	2	1	0

바로 위와 같이 해당 크기의 원소를 만나는 경우 숫자를 1씩 더해가면 된다. 똑같은 방식을 반복하면 결과적으로 다음과 같이 된다.

이제 크기 1부터 5까지 해당 숫자만큼 출력하면 정렬은 끝난다. 즉, 1을 8번, 2를 6번, 3을 8번, 4를 4번, 그리고 5를 4번 출력하면 정렬이 이루어진다.

정렬 후 : 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5

계수 정렬 시간 복잡도

---

계수 정렬은 배열에 있는 원소들의 개수만 세고 작은 수부터 나열하므로 시간 복잡도는 O(n)이다. 조금 더 구체적으로 보자면 시간 복잡도는 O(n + k)라고 할 수 있다. 이때, k는 배열에 있는 최댓값이다. 그리고 공간 복잡도는 k만큼의 배열을 추가로 만들어야 하기 때문에 O(k)라고 할 수 있다.

• 시간 복잡도 : O(n + k)
• 공간 복잡도 : O(k)

계수 정렬 장단점

---

• 장점
  데이터의 범위가 작을 때는 O(n)의 시간 복잡도를 가지므로 매우 빠르다
• 단점
  데이터의 범위가 크면 만들어야 하는 배열의 크기가 크므로 메모리의 낭비가 심하다

출처

https://propercoding.tistory.com/199
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/Sort_Counting.md