Counting sort (계수정렬) 알고리즘

테스트 케이스의 개수가 10,000,000 정도로 매우 많고, 수의 범위가 1~10000으로 제한적인 경우 계수정렬을 사용한다.

1. 계수 정렬이란?

• 배열의 인덱스를 특정 데이터의 값으로 여기는 정렬 방법이다
• 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정
• 데이터가 등장한 횟수를 셈

2. 예시

데이터: 3, 1, 6, 2, 9, 1, 4, 8, 0, 2 인 경우

arrayIndex : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
arrayValue : 1 | 2 | 2 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |

3. 코드로 구현

var numArray = Array(repeating: 0, count: 10001)

• 수의 범위를 포함하는 크기의 데이터 배열 만들기

for _ in 0..<num {
    let a = Int(readLine()!)!
    numArray[a] += 1
}

• 데이터를 받아 인덱스에 해당하는 배열의 값을 1만큼 증가시킨다

for i in 0..<numArray.count {
    if numArray[i] != 0 {
        for _ in 0..<numArray[i] {
            print(i)
        }
    }
}

• 해당 인덱스의 값이 0이 아닌 경우 인덱스를 출력한다.

문제 : 백준 10989