はじめに

こんにちは，光岡です．このブログはとある大学院の研究室メンバーによるブログです！ 3人体制で各々が月に1回ずつ，研究分野問わず自分が興味を持っていることについて発信していきます．そして今回は第一回目の投稿になります！

私はWebサービス開発を勉強していることもあり，今Go言語に興味があります．また，本研究室は情報系の学域ではないため（デザインよりの学域です），最近は個人的にアルゴリズムを学んでいます．アルゴリズムとデータ構造の勉強をする際はC言語やPythonが主流だと思いますが，今回は私が興味を持っている2つを掛け合わせて，Go言語のソートアルゴリズムに関して書いていきたいと思います．

はじめに
Go言語とは
実装
さいごに
参考記事

Go言語とは

Go言語とは，Googleによって設計されたプログラミング言語です． Go言語の主な特徴は以下になります．

静的型付け言語
並列処理が得意
コンパイルが高速

個人的にはこれまで動的型付け言語を触ってきていたので，最初の型定義が少し面倒だなと感じていましたが，今では型がないと、このメソッドの引数・返り値の型はなんだろう..とたまになってしまうので，型が欲しいなと思うようになりました．

また，最初Go言語で書かれたコードを読んだ時，:=記法を理解していなかったのですが，こちらはvarを省略した記法になります．

// 型を宣言
var n int // n = 0 （Go言語の変数は必ず初期化され，ゼロ値が入ります）

// 型推論
var n = 1

// varを省略
n := 1

実装

今回は，選択ソート，挿入ソート，シェルソート，クイックソートの4種を実装してみました．

選択ソート

ソートのアルゴリズムの一つ。配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。最悪時間計算量は O(n2) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。

選択ソートは以下の手順で行う：

1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる）

以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する

すべての要素がソート済みになったら処理を終了する

選択ソート - Wikipedia

for文で最も小さい値のインデックスをmin_idxに代入していき，最終的に格納されていたインデックスを使用して，スライスの要素を順に昇順に並び替えました．

スライスとは
他の言語では，配列を使用しますが，Go言語ではスライスを使用するほうが一般的です．配列とスライスの違いは，配列はサイズが固定長，スライスが可変長です．

package main

import "fmt"

func SelectionSort(nums []int) []int {
    for i := range nums {
        min_idx := i

        for j := i; j < len(nums); j++ {
            if nums[min_idx] > nums[j] {
                min_idx = j
            }
        }
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    }
    return nums
}

func main() {
    nums := []int{2, 4, 3, 1, 5, 7, 6}
    fmt.Println(SelectionSort(nums)) // [1 2 3 4 5 6 7]
}

挿入ソート

数値の列を先頭から小さい順（昇順）に並べる場合を考える。まず、先頭から2つの値を比較して小さい方を先頭に、大きい方を2番目に置く。次に3番目の値を取り出し、先頭・2番目と順に比較し、適切な位置に挿入する。

4番目以降も同様にして、n番目の値を取り出して先頭からn-1番目までと順番に比較し、適切な位置に挿入する操作を繰り返す。

挿入ソート（基本挿入法 / インサーションソート）とは - IT用語辞典 e-Words

未整列の要素が逆順に近い並びの場合は，計算時間が多くかかってしまい，それを緩和したアルゴリズムがシェルソート（後述）になります．

下記コードでは，tempに格納した値を，条件が当てはまる限り適切な位置まで移動させるのがポイントになります．

最初の状態[4, 3, 1, ...]において，i = 1 の時に並び替えると，[3, 4, 1, ...]となります．
次に i = 2 の時，temp = nums[2] = 1が入ります．この時 4 > temp(=1) により，nums[2] に 4 を移動させた後 j をデクリメントして，3 と temp(=1)を比較します． 3 > temp(=1) により，同様に nums[1] に 3 を移動させ，1 が nums[0] に移動し，[1, 3, 4, ...]となります．

このように，比較対象になった値は，適切な位置まで移動し切ってから次の要素を並び替えます．

package main

import "fmt"

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

func main() {
    nums := []int{4, 3, 1, 5, 7, 6, 2}
    fmt.Println(InsertionSort(nums)) // [1 2 3 4 5 6 7]
}

シェルソート

挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。

主な手順は以下の通りです．

適当な間隔 h を決める

間隔 h をあけて取り出したデータ列に挿入ソートを適用する

間隔 h を狭めて、2.を適用する操作を繰り返す

h = 1 になったら、最後に挿入ソートを適用して終了

シェルソート - Wikipedia

間隔の決め方については，様々な方法がありますが，今回は，まずスライスの要素数 / 2 で始め，都度2で割って間隔を狭めていく方法をとって実装してみました．

今回は数値を2で割る際に，ビット演算子の右シフトを使用してみました．

// example

num := 50
fmt.Printf("Result: %06b ( = %d )\n", num, num)          // 110010 ( = 50 )
fmt.Printf("Result: %06b ( = %d )\n", num>>1, num>>1)    // 011001 ( = 25 )
fmt.Printf("Result: %06b ( = %d )\n", num>>2, num>>2)    // 001100 ( = 12 )

package main

import "fmt"

func ShellSort(nums []int) []int {
    n := len(nums)
    h := n >> 1

    for h > 0 {
        for i := h; i < n; i++ {
            for j := i; j >= h; j -= h {
                if nums[j-h] > nums[j] {
                    nums[j], nums[j-h] = nums[j-h], nums[j]
                }
            }
        }
        h >>= 1
    }
    return nums
}

func main() {
    nums := []int{4, 3, 1, 5, 7, 6, 2}
    fmt.Println(ShellSort(nums)) // [1 2 3 4 5 6 7]
}

クイックソート

クイックソートとは分割統治法の1つです．主な手順は以下の通りです．

ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する

配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する

再帰：分割された区間に対し、再びピボットの選択と分割を行う

ソート終了：分割区間が整列済みなら再帰を打ち切る

クイックソート - Wikipedia

文章のみの説明だとイメージしづらいと思います．個人的にはクイックソートとは | 分かりやすく図解で解説の図解がとてもわかりやすかったので，是非確認してみてください！

他のソートアルゴリズムに比べ，高速だと言われていますが，手順1のピボットの位置やデータの並びによっては計算量が多くなることもあります．

今回のピボットは，スライスの最後の要素を使用して実装してみました．また，partitionメソッドの返り値i + 1は pivot に指定していた値の最終的な位置を返しており，その pivot よりインデックスが小さいスライスと大きいスライスの2つに分け，再帰的に同じ処理を行い並び替えを行っています．

package main

import (
    "fmt"
)

func partition(nums []int, low int, high int) int {
    i := low - 1
    pivot := nums[high]
    for j := low; j < high; j++ {
        if nums[j] <= pivot {
            i++
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    nums[i+1], nums[high] = nums[high], nums[i+1]
    return i + 1
}

func QuickSort(nums []int, low int, high int) []int {
    if low < high {
        partition_idx := partition(nums, low, high)
        QuickSort(nums, low, partition_idx-1)
        QuickSort(nums, partition_idx+1, high)
    }
    return nums
}

func main() {
    nums := []int{2, 4, 3, 1, 5, 7, 6}
    low := 0
    high := len(nums) - 1
    fmt.Println(QuickSort(nums, low, high)) // [1 2 3 4 5 6 7]
}

さいごに

今回は基本のソートアルゴリズム4種をGo言語で実装してみました．これまでアルゴリズムをしっかり学んだことがなかったのですが，楽しみながら学ぶことができました．まだ次回内容は決めていませんが，他のアルゴリズムも取り上げてみたいと思います．

ネットワークデザインスタジオのブログ

Go言語で基本のソートアルゴリズムを実装してみた