【Go】Sorting algorithms (ソートアルゴリズム)

Goでプログラミングの基礎を学ぶシリーズ

スクールでは教えてくれないプログラミングの基礎、データ構造とアルゴリズムをGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単な説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。

	タイトル
#0	はじめに (環境構築と勉強方法)
#1	Pointer, Array, String (ポインタと配列と文字列と)
#2	File operations (ファイル操作)
#3	Linked List (連結リスト)
#4	Stack & Queue (スタックとキュー)
#5	Search algorithms (探索アルゴリズム)
#6	Tree (木構造)
#7	Sorting algorithms (ソートアルゴリズム) ☜ here
#8	String pattern matching algorithms (文字列探索アルゴリズム)

今回は#7 Sorting algorithms (ソートアルゴリズム)です。

Sortとは

データを一定の規則に従って並び替えることです。
昇順や降順など日常生活でも馴染みがありますね。
Sort には多くのアルゴリズムが存在し、時間計算量が比較されます。
以下の記事はソートの様子が可視化されているので、直感的にわかりやすいと思います。

ここでは中でも代表的な Sort のアルゴリズムの Go での実装例をみていきます。
各ソートがどのような流れでソートしていくかは、上のサイトをご参考ください。

Insertion sort (挿入ソート)

リストのソート済みの部分に、新たな要素を適切な位置に挿入することを繰り返してソートを行うアルゴリズムです。
平均計算時間: $O(n^2)$ , 最悪計算時間: $O(n^2)$ と遅いのですが、アルゴリズムは単純で実装しやすいと思います。

func InsertionSort(numbers []int) []int {
    for i := 0; i < len(numbers); i++ {
        next := numbers[i] // ソートされていない部分の先頭

        fmt.Printf("next: %d\n", next)

        var j int
        // ソートされている部分で、 next が挿入されるところまで要素をずらしていく
        for j = i - 1; j >= 0 && next < numbers[j]; j-- {
            numbers[j+1] = numbers[j]

            fmt.Printf("j = %d, sorting... %v\n", j, numbers)
        }
        numbers[j+1] = next // next を挿入

        fmt.Printf("after insert next: %v\n\n", numbers)
    }
    return numbers
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    InsertionSort(numbers)
}

所々にログを仕込んでみました。
ログを見ると、ソートの流れがよくわかるかと思います。

☟ 出力結果

next: 7
after insert next: [7 65 8 32 4 21 10]

next: 65
after insert next: [7 65 8 32 4 21 10]

next: 8
j = 1, sorting... [7 65 65 32 4 21 10]
after insert next: [7 8 65 32 4 21 10]

next: 32
j = 2, sorting... [7 8 65 65 4 21 10]
after insert next: [7 8 32 65 4 21 10]

next: 4
j = 3, sorting... [7 8 32 65 65 21 10]
j = 2, sorting... [7 8 32 32 65 21 10]
j = 1, sorting... [7 8 8 32 65 21 10]
j = 0, sorting... [7 7 8 32 65 21 10]
after insert next: [4 7 8 32 65 21 10]

next: 21
j = 4, sorting... [4 7 8 32 65 65 10]
j = 3, sorting... [4 7 8 32 32 65 10]
after insert next: [4 7 8 21 32 65 10]

next: 10
j = 5, sorting... [4 7 8 21 32 65 65]
j = 4, sorting... [4 7 8 21 32 32 65]
j = 3, sorting... [4 7 8 21 21 32 65]
after insert next: [4 7 8 10 21 32 65]

Selection sort (選択ソート)

リストのソートされていない部分から、最小値(or最大値)を持つ要素を探して、その値をソートされていない部分の先頭に移動(交換)することを繰り返してソートを行うアルゴリズムです。
平均計算時間: $O(n^2)$ , 最悪計算時間: $O(n^2)$ と遅いのですが、アルゴリズムは単純で実装しやすいと思います。

func SelectionSort(numbers []int) []int {
    for i := 0; i < len(numbers); i++ {
        min := i
        // ソートされていない部分での最小値の index を探す
        for j := i + 1; j < len(numbers); j++ {
            if numbers[min] > numbers[j] {
                min = j
            }
        }
        // ソートされていない部分の先頭と、ソートされていない部分での最小値を入れ替える
        numbers[i], numbers[min] = numbers[min], numbers[i]

        fmt.Printf("i = %d, %v\n", i, numbers)
    }
    return numbers
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    SelectionSort(numbers)
}

☟ 出力結果

i = 0, [4 65 8 32 7 21 10]
i = 1, [4 7 8 32 65 21 10]
i = 2, [4 7 8 32 65 21 10]
i = 3, [4 7 8 10 65 21 32]
i = 4, [4 7 8 10 21 65 32]
i = 5, [4 7 8 10 21 32 65]
i = 6, [4 7 8 10 21 32 65]

Bubble sort (バブルソート)

隣り合う要素の大小を比較しながらソートしていくアルゴリズムです。
平均計算時間: $O(n^2)$ , 最悪計算時間: $O(n^2)$ と遅いのですが、アルゴリズムは単純で実装しやすいと思います。

func BubbleSort(numbers []int) []int {
    for i := 0; i < len(numbers)-1; i++ {
        for j := 0; j < len(numbers)-i-1; j++ {
            if numbers[j] > numbers[j+1] {
                numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
            }
        }
        fmt.Printf("i = %d, %v\n", i, numbers)
    }
    return numbers
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    BubbleSort(numbers)
}

☟ 出力結果

i = 0, [7 8 32 4 21 10 65]
i = 1, [7 8 4 21 10 32 65]
i = 2, [7 4 8 10 21 32 65]
i = 3, [4 7 8 10 21 32 65]
i = 4, [4 7 8 10 21 32 65]
i = 5, [4 7 8 10 21 32 65]

Heap sort (ヒープソート)

ヒープとは、データ構造の一種で、木構造（ツリー構造）のうち、親要素が子要素より常に大きい（あるいは小さい）という条件を満たすもの。
引用: IT用語辞典 e-Words

Heap sort は Binary Heap (二分ヒープ木) を用いて行うソートのアルゴリズムです。
ヒープの構造を利用するだけで、Tree を実装する必要はありません。
平均計算時間: $O(n\log{n})$ , 最悪計算時間: $O(n\log{n})$ であり、上の3つよりも速いソートアルゴリズムになります。

func HeapSort(numbers []int) []int {
    // heap を形成する
    fmt.Printf("Build Heap\n")
    for i := len(numbers)/2 - 1; i >= 0; i-- {
        heapify(numbers, len(numbers), i)
    }

    // heap から要素を一つずつ取り出す (ソートしていく)
    fmt.Printf("\nHeap Sort")
    for i := len(numbers) - 1; i > 0; i-- {
        numbers[i], numbers[0] = numbers[0], numbers[i]

        fmt.Printf("\ni = %d, sorting... %v\n", i, numbers)

        heapify(numbers, i, 0)
    }
    return numbers
}

// i 番目の要素を root とする Tree をヒープ化する.
// len は heap size, root は numbers の index
func heapify(numbers []int, len, root int) {
    largest := root // 最大の要素の index を i (root) としておく
    left := 2*root + 1
    right := 2*root + 2

    if left < len && numbers[left] > numbers[largest] { // left child が root より大きい場合
        largest = left
    }
    if right < len && numbers[right] > numbers[largest] { // right child が root より大きい場合
        largest = right
    }
    if largest != root { // 最大の要素が root ではないとき
        numbers[root], numbers[largest] = numbers[largest], numbers[root] // root の要素と最大の要素を入れ替える

        fmt.Printf("(%d %d %d) heapify... %v\n", root, left, right, numbers)

        heapify(numbers, len, largest)
    }
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    HeapSort(numbers)
}

☟ 出力結果

Build Heap
(2 5 6) heapify... [7 65 21 32 4 8 10]
(0 1 2) heapify... [65 7 21 32 4 8 10]
(1 3 4) heapify... [65 32 21 7 4 8 10]

Heap Sort
i = 6, sorting... [10 32 21 7 4 8 65]
(0 1 2) heapify... [32 10 21 7 4 8 65]

i = 5, sorting... [8 10 21 7 4 32 65]
(0 1 2) heapify... [21 10 8 7 4 32 65]

i = 4, sorting... [4 10 8 7 21 32 65]
(0 1 2) heapify... [10 4 8 7 21 32 65]
(1 3 4) heapify... [10 7 8 4 21 32 65]

i = 3, sorting... [4 7 8 10 21 32 65]
(0 1 2) heapify... [8 7 4 10 21 32 65]

i = 2, sorting... [4 7 8 10 21 32 65]
(0 1 2) heapify... [7 4 8 10 21 32 65]

i = 1, sorting... [4 7 8 10 21 32 65]

流れを図にすると以下のようになります。

まずはランダムな配列のヒープ化を行います。
heapify　では root, left, right から最大の値を root と入れ替え、入れ替えが行われた index について再帰的に heapify を実行するという流れになります。

ヒープ化ができたらソートをしていきます。
ヒープ化により root が最大値になっているので、root と配列の最後尾を入れ替え、入れ替えが行われた後に再度ヒープ化( heapify )を実行します。
それの繰り返しにより、ソートされていきます。

Quick sort (クイックソート)

ピボットという基準となる値をランダムに選択し、リストの先頭からピボットよりも大きいか小さいかで両側のグループに分割し、それを繰り返してソートを行うアルゴリズムです。
平均計算時間: $O(n\log{n})$ , 最悪計算時間: $O(n^2)$ であり、Wikipediaによると、
他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではない ようです。

func QuickSort(numbers []int) []int {
    if len(numbers) < 2 {
        return numbers
    }

    fmt.Printf("\nsorting... %v\n", numbers)

    left, right := 0, len(numbers)-1
    pivot := numbers[right]

    for i := 0; i < right; i++ {
        if numbers[i] < pivot {
            numbers[i], numbers[left] = numbers[left], numbers[i]
            left++

            fmt.Printf("p = %d, left = %d, %v\n", pivot, numbers[left], numbers)
        }
    }
    numbers[left], numbers[right] = numbers[right], numbers[left]

    fmt.Printf("p = %d, left = %d, %v\n", pivot, numbers[left], numbers)

    QuickSort(numbers[:left])
    QuickSort(numbers[left+1:])
    return numbers
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    QuickSort(numbers)
}

☟ 出力結果

sorting... [7 65 8 32 4 21 10]
p = 10, left = 65, [7 65 8 32 4 21 10]
p = 10, left = 65, [7 8 65 32 4 21 10]
p = 10, left = 32, [7 8 4 32 65 21 10]
p = 10, left = 10, [7 8 4 10 65 21 32]

sorting... [7 8 4]
p = 4, left = 4, [4 8 7]

sorting... [8 7]
p = 7, left = 7, [7 8]

sorting... [65 21 32]
p = 32, left = 65, [21 65 32]
p = 32, left = 32, [21 32 65]

ソートの流れは最初にリンクした参考サイトの通りです。

Merge sort (マージソート)

ソートされていないリストを2つのリストに分割して、それぞれをソートした後、それらをマージしてソート済みのひとつのリストを作るアルゴリズムです。
平均計算時間: $O(n\log{n})$ , 最悪計算時間: $O(n\log{n})$

func MergeSort(numbers []int) []int {
    if len(numbers) < 2 {
        return numbers
    }
    middle := len(numbers) / 2
    return merge(MergeSort(numbers[:middle]), MergeSort(numbers[middle:]))
}

func merge(left, right []int) []int {
    var merged []int
    fmt.Printf("\nmerge %v %v\n", left, right)

    // 左のリストと右のリストの要素を比較し、小さい方を merged に追加する
    for i := 0; len(left) > 0 && len(right) > 0; i++ {
        if left[0] < right[0] {
            merged = append(merged, left[0])
            left = left[1:]
        } else {
            merged = append(merged, right[0])
            right = right[1:]
        }
        fmt.Printf("i = %d, %v\n", i, merged)
    }

    // リストに残っている要素を merged に追加
    for _, l := range left {
        merged = append(merged, l)
    }
    for _, r := range right {
        merged = append(merged, r)
    }

    fmt.Printf("sorted %v\n", merged)
    return merged
}

func main() {
    numbers := []int{7, 65, 8, 32, 4, 21, 10}
    MergeSort(numbers)
}

☟ 出力結果

merge [65] [8]
i = 0, [8]
sorted [8 65]

merge [7] [8 65]
i = 0, [7]
sorted [7 8 65]

merge [32] [4]
i = 0, [4]
sorted [4 32]

merge [21] [10]
i = 0, [10]
sorted [10 21]

merge [4 32] [10 21]
i = 0, [4]
i = 1, [4 10]
i = 2, [4 10 21]
sorted [4 10 21 32]

merge [7 8 65] [4 10 21 32]
i = 0, [4]
i = 1, [4 7]
i = 2, [4 7 8]
i = 3, [4 7 8 10]
i = 4, [4 7 8 10 21]
i = 5, [4 7 8 10 21 32]
sorted [4 7 8 10 21 32 65]

ソートの流れは最初にリンクした参考サイトの通りです。

💻 Exercise

1~500 の数字で構成される、要素数 500 のランダムな配列を Insertion sort と　Quick sort でソートしましょう。
その実行速度を比較してみましょう。

☟ 解答例

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func initList(n int) []int {
    var numbers []int
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < n; i++ {
        numbers = append(numbers, rand.Intn(500))
    }
    return numbers
}

func InsertionSort(numbers []int) []int {
    for i := 0; i < len(numbers); i++ {
        next := numbers[i]
        var j int
        for j = i - 1; j >= 0 && next < numbers[j]; j-- {
            numbers[j+1] = numbers[j]
        }
        numbers[j+1] = next
    }
    return numbers
}

func QuickSort(numbers []int) []int {
    if len(numbers) < 2 {
        return numbers
    }
    left, right := 0, len(numbers)-1
    pivot := numbers[right]

    for i := 0; i < right; i++ {
        if numbers[i] < pivot {
            numbers[i], numbers[left] = numbers[left], numbers[i]
            left++
        }
    }
    numbers[left], numbers[right] = numbers[right], numbers[left]

    QuickSort(numbers[:left])
    QuickSort(numbers[left+1:])
    return numbers
}

func main() {
    numbers := initList(500)
    start := time.Now()
    InsertionSort(numbers)
    runtime := time.Since(start)
    fmt.Printf("Insertion sort ▶︎ runtime: %v\n", runtime)

    numbers = initList(500)
    start = time.Now()
    QuickSort(numbers)
    runtime = time.Since(start)
    fmt.Printf("Quick sort ▶︎ runtime: %v\n", runtime)
}

☟ 出力結果

Insertion sort ▶︎ runtime: 44.611µs
Quick sort ▶︎ runtime: 23.602µs

おわりに

Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！
説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。

株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。
未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！
絶賛エンジニア募集中です！
Wantedly ▶︎ https://www.wantedly.com/projects/324177
Green ▶︎ https://www.green-japan.com/job/82003

次回は、データ構造とアルゴリズム#8 String pattern matching algorithms (文字列探索アルゴリズム)です。