Counting Sort - 계수 정렬

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

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

Counting sort - Wikipedia

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

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

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)
}

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

원본 배열(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로 정렬해야 한다면 가장 작은 음의 정수를 확인해 그 만큼의 배열을 만들어서 처리해 줘야 합니다.