계수 정렬(Counting Sort)

계수 정렬은 작은 정수 키를 기준으로 객체 컬렉션을 정렬하는 알고리즘이다. 각 고유 키 값에 해당하는 객체의 수를 세고, 그 수를 기반으로 산술 연산을 수행해 출력 시퀀스에서 각 키 값의 위치를 결정한다.

예제

알고리즘을 이해하기 위해 간단한 예제를 살펴보자.

다음 배열을 생각해 보자: [ 10, 9, 8, 7, 1, 2, 7, 3 ]

1단계:

첫 번째 단계는 배열의 각 항목이 몇 번 등장하는지 총 횟수를 세는 것이다. 첫 번째 단계의 결과는 다음과 같은 새로운 배열이 된다:

Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1

이를 구현하는 코드는 다음과 같다:

  let maxElement = array.max() ?? 0

  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
  for element in array {
    countArray[element] += 1
  }

이 단계에서는 알고리즘이 각 엘리먼트 앞에 위치한 엘리먼트의 수를 계산한다. 이미 각 엘리먼트의 총 발생 횟수를 알고 있기 때문에 이 정보를 활용할 수 있다. 이전 카운트를 합산해 각 인덱스에 저장하는 방식으로 동작한다.

카운트 배열은 다음과 같다:

Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 2 3 3 3 3 5 6 7 8

이 단계의 코드는 다음과 같다:

  for index in 1 ..< countArray.count {
    let sum = countArray[index] + countArray[index - 1]
    countArray[index] = sum
  }

3단계:

이 단계는 알고리즘의 마지막 단계이다. 원본 배열의 각 요소를 2단계에서 정의한 위치에 배치한다. 예를 들어, 숫자 10은 출력 배열의 인덱스 7에 위치하게 된다. 또한 요소를 배치할 때마다 카운트를 1씩 감소시켜야 한다. 이는 배열에서 해당 요소가 제거되었음을 의미한다.

새로 정렬된 배열의 안정성을 유지하기 위해 배열을 역순으로 반복해야 한다. 예를 들어, 7은 인덱스 3과 6에 위치하므로, sortedArray에서 인덱스 3에 있는 7은 인덱스 6에 있는 7보다 앞에 위치해야 한다.

최종 출력은 다음과 같다:

인덱스 0 1 2 3 4 5 6 7
출력   1 2 3 7 7 8 9 10

이 마지막 단계를 구현한 코드는 다음과 같다:

var sortedArray = [Int](repeating: 0, count: array.count)
for index in stride(from: array.count - 1, through: 0, by: -1) {
  let element = array[index]
  countArray[element] -= 1
  sortedArray[countArray[element]] = element
}
return sortedArray

성능

이 알고리즘은 컬렉션을 정렬하기 위해 단순한 반복문을 사용한다. 따라서 전체 알고리즘을 실행하는 데 걸리는 시간은 **O(n+k)**이다. 여기서 **O(n)**은 출력 배열을 초기화하는 데 필요한 반복문을 나타내고, **O(k)**는 카운트 배열을 생성하는 데 필요한 반복문을 나타낸다.

알고리즘은 길이가 n + 1과 n인 배열을 사용하므로 필요한 전체 공간은 **O(2n)**이다. 따라서 키가 수직선 상에 조밀하게 분포된 컬렉션의 경우 공간 효율적일 수 있다.

Swift Algorithm Club을 위해 Ali Hafizji가 작성함