Go 標準のソート・アルゴリズム

公開:2020/09/26
更新:2020/09/26
3 min読了の目安(約2200字TECH技術記事

今回は

から着想を得て Go 標準の sort パッケージについて簡単に紹介する。なお今回の記事は,以前 LT 用に書いたスライド「配列とスライスとソート」からの抜粋となっている。よろしければスライドの方もご笑覧あれ。

まずはコード

Go 標準の sort パッケージでは任意の slice ソートについて以下のように記述できる。

package main

import (
    "fmt"
    "sort"
)

func main() {
    ds := []float64{0.055, 0.815, 1.0, 0.107}
    fmt.Println(ds) //before
    sort.Slice(ds, func(i, j int) bool {
        return ds[i] < ds[j]
    })
    fmt.Println(ds) //after
}

このコードの実行結果は以下の通り。

[0.055 0.815 1 0.107]
[0.055 0.107 0.815 1]

sort パッケージでは slice に対して2種類のソート関数を用意していて

このうち sort.SliceStable() 関数のほうを安定ソート(挿入ソート)として記述がされている。

Sort パッケージで使われているアルゴリズム

Sort パッケージの sort.Slice() 関数では以下のように複数のアルゴリズムを使い分けている。

  1. 基本はクイックソート
  2. 要素数が12以下ならシェルソート(gap 6)へ
  3. 要素数が6以下なら挿入ソート
  4. クイックソートの再帰レベルが一定を超えたらヒープソートへ(イントロソート
    • depth=lb(n+1)×2depth = \lceil \mathrm{lb}(n+1)\rceil\times 2

ちなみにアルゴリズム毎の計算量は以下のとおりである。

名前 最良 最悪 平均
クイックソート O(nlogn)\mathrm{O}(n \log n) O(n2)\mathrm{O}(n^2) O(nlogn)\mathrm{O}(n \log n)
ヒープソート O(nlogn)\mathrm{O}(n \log n) O(nlogn)\mathrm{O}(n \log n) O(nlogn)\mathrm{O}(n \log n)
シェルソート O(nlog2n)\mathrm{O}(n \log^2 n) O(n2)\mathrm{O}(n^2)
挿入ソート O(n)\mathrm{O}(n) O(n2)\mathrm{O}(n^2) O(n2)\mathrm{O}(n^2)