Counting Sort (계수 정렬)

Counting sort 는 배열의 값을 비교하면서 정렬하는게 아닌

 

해당 숫자의 값을 Counting 해서 순서대로 출력해주는 정렬이며 Stable(안정) sort 입니다.

 

상당히 빠른 속도를 보여주지만 메모리를 많이 잡아 먹게 돼 배열의 Max value가 낮은 경우에 사용하기 좋습니다.

 

import Foundation

// 정렬해야하는 배열
var arr = [10, 9, 8, 7, 1, 2, 7, 3]
// 숫자가 몇개 들어있는지 카운트해주는 배열
var count = [Int](repeating: 0, count: arr.max()!+1) // 해당 배열 중 가장 큰 값을 찾아줌
// 정렬된 배열
var sort = [Int](repeating: 0, count: arr.count)

// 숫자 카운트
for i in arr {
    count[i] += 1
}

// 앞의 값과 현재의 값을 더해줌
for i in 1..<count.count {
    count[i] = count[i - 1] + count[i]
}

// 더해준 값에서 1을 빼주고, arr 값을 count[i] 번째에 넣어줌
for i in arr {
    count[i] -= 1	
    sort[count[i]] = i
}

print(sort)