カウントソートの実装｜O(n+k)の整列をGoで

比較を使わずにソートするカウントソートを、実装を通じて学ぶ記事。要素をカウントして累積和を求めることで線形時間O(n)を実現する仕組みを、Goでの実装例とともに、その数学的な考え方から解説する。

Read in: en

カウントソートとは

ソートアルゴリズムの中でも比較を使わずにソートする変わった？アルゴリズム。

比較せずに要素をカウントすることでソートができる。

カウントしてソートすることができるというのは不思議！と思ったので調べてみた。

前提

累積和について知っておく必要がある。

cf. qiita.com - 累積和とは（超初心者用）

実装

ソースコードは以下。

count_sort

package main

import "fmt"

func countSort(s []int, maxVal int) []int {
	count := make([]int, maxVal+1)

	// カウント
	for _, num := range s {
		count[num]++
	}

	// 累積和計算
	// ex. [1, 2, 3, 4, 5] →　[1, 3, 6, 10, 15]
	for i := 1; i <= maxVal; i++ {
		count[i] += count[i-1]
	}

	sorted := make([]int, len(s))

	// 元の配列を末尾から走査し、要素をソート結果に配置
	for i := len(s) - 1; i >= 0; i-- {
		num := s[i]
		count[num]--
		sorted[count[num]] = num
	}

	return sorted
}

func main() {
	s := []int{5, 3, 2, 1, 2, 3, 4}
	maxVal := 5
	r := countSort(s, maxVal)
	fmt.Println(r)
}