Counting Sort - 계수 정렬

Counting Sort는 값을 비교해 정렬하는 방식이 아닌 Key Value 형태의 계산으로 정렬합니다.

https://en.wikipedia.org/wiki/Counting_sort

Counting sort - Wikipedia

정렬하려는 배열에서 동일한 값이 몇가가 있는지를 확인하고 그 값을 자릿수로 확인합니다.
다시말해, 자릿수를 key, 자릿수에 해당하는 값의 카운트를 값으로 갖는 배열을 생성하고 그에 맞게 정렬하게 됩니다.

먼저 Go로 구현된 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package main
import "fmt"
// 배열에서 가장 큰 수에 1을 더해 리턴합니다.
// Key로 사용할 배열의 길이를 확인합니다.
func getK(arr [12]int) int {
    if len(arr) == 0 {
        return 1
    }
    k := arr[0]
    for _, v := range arr {
        if v > k {
            k = v
        }
    }
    return k + 1
}
func main() {
    arr := [12]int{9, 1, 2, 8, 6, 7, 5, 3, 1, 4, 5, 12}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    k := getK(arr)
    // 정렬하려는 배열의 가장 큰 값 +1의 길이로 slice를 만듭니다.
    arrayOfCounts := make([]int, k)
    // arrayOfCounts 배열에 정렬하려는 배열의 값을 카운팅해 입력합니다.
    for i := 0; i < len(arr); i++ {
        arrayOfCounts[arr[i]]++
    }
    for i, j := 0, 0; i < k; i++ {
        for {
            // arrayOfCounts 배열의 0번째 자리부터 마지막까지 Loop를 돌며 0 이상인 것을 찾습니다.
            if arrayOfCounts[i] > 0 {
                // 정렬하려는 배열의 자릿수에 i값을 넣습니다.
                arr[j] = i
                j++
                // arrayOfCounts 배열의 i번째 자리의 값에서 1을 뺍니다.
                arrayOfCounts[i]--
                continue
            }
            // arrayOfCounts의 값이 0이라면 loop를 종료합니다.
            break
        }
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

정렬하려는 배열이 아래와 같이 있을 경우 배열의 값을 자릿수로하는 배열을 만들어 줍니다.

원본 배열(arr)    [9, 1, 2, 8, 6, 7, 5, 3, 1, 4, 5, 12]
카운트한 배열    [0, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 1]

카운트한 배열이 [0, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 1]일때 자릿값 0은 원본 배열의 값 중 0이 0번 카운트 되었다는 것을 의미합니다.
마찬가지로 원본 배열의 값 중 1은 2번, 3은 1번, 4는 1번, 5는 2번... 10은 0번, 11은 0번, 12는 1번입니다.

만약 원본 배열이 [9, 1, 2, 8, 6, 7, 5, 3, 1, 4, 5, 20]라면 가장 큰 수인 20에 +1의 자릿수를 가진 배열을 만들어 줘야합니다. 그리고 그 값은 [0, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 이렇게 될 것입니다.

그래서 Counting Sort는 몇 가지 재약이 있습니다.
정렬하려는 값이 모두 양의 정수여야합니다. 그리고 가장 큰 수만큼의 배열을 만들어야 하니 메모리 소비도 많습니다.

음의 정수까지 Counting Sort로 정렬해야 한다면 가장 작은 음의 정수를 확인해 그 만큼의 배열을 만들어서 처리해 줘야 합니다.