ソートアルゴリズムをGoで実装してみた

はじめに

バックエンドエンジニアのロードマップに沿ってエンジニアとしての自己肯定感を養うシリーズです。

マージソート

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を 1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

出典：wikipedia「マージソート」より引用

最悪の計算量が O(n log n) であるから少なくとも O(n^2)よりは速いんだろうなという印象（雑すぎるか）

以下「ソートを極める！ 〜 なぜソートを学ぶのか 〜」を元に実装してみた（なるべくソースを見ないで実装を試みたがマージする箇所は折れた、、）

package main

import (
"fmt"
"time"

    "github.com/uh-zz/traning/algorithm/shuffle"

)

func main() {
// ランダムな要素 n 個のスライス取得
input := shuffle.RandomIntList(n)

    inputLength := len(input)

// マージソート
MergeSort(&input, 0, inputLength)
}

// MergeSort マージソート
func MergeSort(input \*[]int, left, right int) {

    // 要素数1つの場合は抜ける
    if right-left == 1 {
    	return
    }

// 配列を２つに分けるインデックス
middle := left + (right-left)/2

// 配列左側
MergeSort(input, left, middle)
// 配列右側
MergeSort(input, middle, right)

    var buffer []int

    // 左側と右側をバッファにためる（右側反転）
    for index := left; index < middle; index++ {
    	buffer = append(buffer, (*input)[index])
    }
    for index := right - 1; index >= middle; index-- {
    	buffer = append(buffer, (*input)[index])
    }

    // マージする
    scopeLeft := 0
    scopeRight := len(buffer) - 1
    for index := left; index < right; index++ {

    	if buffer[scopeLeft] <= buffer[scopeRight] {
    		// 左側採用
    		(*input)[index] = buffer[scopeLeft]
    		scopeLeft++
    	} else {
    		// 右側採用
    		(*input)[index] = buffer[scopeRight]
    		scopeRight--
    	}
    }

}

これ考えたのぶっ飛んでるなあと思って Wikipedia 見てたら、考案者がフォン・ノイマンでやっぱりぶっ飛んでた（凄すぎ）

挿入ソート

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともに O(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-place アルゴリズムであり、オンラインアルゴリズムである。

出典：wikipedia「挿入ソート」より引用

これも「ソートを極める！ 〜 なぜソートを学ぶのか 〜」を元に実装してみた

package main

import (
"fmt"
"time"

    "github.com/uh-zz/traning/algorithm/shuffle"

)

func main() {

// ランダムな要素 n 個のスライス
input := shuffle.RandomIntList(n)

    // 挿入ソート
    for index := 1; index < len(input); index++ {

    	// 挿入したい値
    	insertValue := input[index]

    	// 挿入位置
    	point := index
    	for ; point > 0; point-- {
    		if input[point-1] > insertValue {
    			input[point] = input[point-1]
    		} else {
    			break
    		}
    	}
    	input[point] = insertValue
    }

}

こっちは実装もしやすく理解するのも難しくないという印象。最終的にはどちらもソートするというのにこの差は、、と思ってしまう。

速度比較

今回はソートアルゴリズムの実装がメインだったけど、２つあるなら比較するまでがアウトプットだろうなと感じたので比較します。

マシンスペック

• OS: macOS Catalina
• プロセッサ: 1.6 GHz(Core i5)
• メモリ: 16 GB

実施方法

要素数 n 個のスライスのソート時間を比較する。要素はそれぞれランダムになっている。

結果

※挿入ソート（1,000,000）は 1 分以上かかったので省略

要素が倍になるほどマージソートの速さがわかりますね。

このページのソースは GitHub にもあります。

ソートアルゴリズムの比較

余談

アルゴリズムを１ヶ月で把握しようとしてましたがソートアルゴリズムの雰囲気を掴むだけでそれくらい時間かかりました、、

１つずつ精進ですね。。