代表的なアルゴリズムをGoで書いてみた

代表的なアルゴリズムをGoを使って学習していた時に、自身のメモとして記述していた内容を改良して記事にしてみました。 Pythonなどで書いている記事はそれなりにあると思いますが、Goで書いている記事は少ない印象でしたので誰かの参考になれば幸いです！！

linear search(リニアサーチ）

線型探索は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。 n個のデータからm個のデータを検索する場合、時間計算量はO(nm)、空間計算量はO(1)である。

func linearSearch(nums []int, value int) int {
    for i, num := range nums {
        if num == value {
            return i
        }
    }
    return -1
}

binary search(バイナリサーチ）

バイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

ソート済みのリストや配列に入ったデータに対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していきます。 大小関係を用いるため、ソートされていないリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできません。

n個のデータがある場合、時間計算量はO(logn） n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができます。

func binarySearch(nums []int, value int) int {
    low := 0
    high := len(nums) - 1

    for low <= high {
        mid := (low + high) / 2

        if nums[mid] == value {
            return mid
        }
        if nums[mid] < value {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

// 再帰を使った、バイナリサーチ
func binarySearchRecursive(nums []int, value int, low, high int) int {
    if low > high {
        return -1
    }
    mid := (low + high) / 2
    if nums[mid] == value {
        return mid
    } else if nums[mid] < value {
        return binarySearchRecursive(nums, value, mid+1, high)
    } else {
        return binarySearchRecursive(nums, value, low, mid-1)
    }
}

bubble sort(バブルソート）

隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。

アルゴリズムが単純で実装も容易である一方、最悪時間計算量は O(n2) と遅いため、一般にはマージソートやヒープソートなど、より最悪時間計算量の高速な方法が利用されるます。

アルゴリズム

要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返すアルゴリズムとなります。

func bubbleSort(nums []int) []int {
    lenNums := len(nums)

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

selection sort(選択ソート）

ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。

最悪時間計算量は O(n2) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。 選択ソートは内部ソートである。また、安定ソートではない。 選択ソートの改良として、ヒープソートが挙げられる。

アルゴリズム

1.1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる） 2.以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する 3.すべての要素がソート済みになったら処理を終了する

func selectionSort(nums []int) []int {
    lenNums := len(nums)

    for i := 0; i < lenNums; i++ {
        minIdx := i
        for j := i + 1; j < lenNums; j++ {
            if nums[minIdx] > nums[j] {
                minIdx = j
            }
        }
        nums[i], nums[minIdx] = nums[minIdx], nums[i]
    }
    return nums
}

insertion sort(挿入ソート）

整列してある配列に追加要素を適切な場所に挿入する。 時間計算量は平均・最悪ケースでともに Ο(n2) であり、クイックソートやマージソートなどと比べれば遅い。 - アルゴリズムが単純で実装が容易 - 小さな配列に対しては高速 - 安定 などの特徴から利用されることがあります。挿入ソートを高速化したソート法として、シェルソートが有名です。

アルゴリズム

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

func insertionSort(nums []int) []int {
    lenNums := len(nums)

    for i := 1; i < lenNums; i++ {
        temp := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > temp {
            nums[j+1] = nums[j]
            j -= 1
        }
        nums[j+1] = temp
    }
    return nums
}

shell sort

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

アルゴリズム

アルゴリズムの基本は挿入ソートと同じ。挿入ソートは「ほとんど整列されたデータに対しては高速」という長所を持つが、隣接した要素同士しか比較・交換を行わないため、あまり整列されていないデータに対しては低速となります。 シェルソートは、「飛び飛びの列を繰り返しソートして、配列を大まかに整列された状態に近づけていく」ことにより、挿入ソートの長所を活かした形のアルゴリズムになります。 アルゴリズムは次の通りです。 1.適当な間隔h を決める（hの決め方については後述） 2.間隔h をあけて取り出したデータ列に挿入ソートを適用する 3.間隔h を狭めて、2.を適用する操作を繰り返す 4.h=1 になったら、最後に挿入ソートを適用して終了

func shellSort(nums []int) []int {
    lenNums := len(nums)
    gap := lenNums / 2

    for gap > 0 {
        for i := gap; i < lenNums; i++ {
            temp := nums[i]
            j := i
            for j >= gap && nums[j-gap] > temp {
                nums[j] = nums[j-gap]
                j -= gap
            }
            nums[j] = temp
        }
        gap /= 2
    }
    return nums
}

Quick sort

n 個のデータをソートする際の最良計算量および平均計算量は、O(n　log n)になります。 他のソート法と比べて一般的に最も高速だと言われているいますが、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n²)になることもあります。

アルゴリズム

1.ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する 2.配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する 3.再帰：分割された区間に対し、再びピボットの選択と分割を行う 4.ソート終了：分割区間が整列済みなら再帰を打ち切る

func partition(nums []int, low, 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, high int) []int {
    if low < high {
        partitionIndex := partition(nums, low, high)
        quickSort(nums, low, partitionIndex-1)
        quickSort(nums, partitionIndex+1, high)
    }
    return nums
}

func quickSortStart(nums []int) []int {
    return quickSort(nums, 0, len(nums)-1)
}

merge sort

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されているというボトムアップの分割統治法。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できます。 n個のデータを含む配列をソートする場合、最悪計算量O(n log n)になります。分割と統合の実装にもよるが、一般に安定なソートを実装できる。 クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。

アルゴリズム

1.データ列を分割する（通常、二等分する） 2.分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする 3.二つのソートされたデータ列（1個であればそれ自身）をマージする

func mergeSort(nums []int) []int {
    var lenNums = len(nums)

    if lenNums == 1 {
        return nums
    }

    mid := lenNums / 2
    var (
        left  = make([]int, mid)
        right = make([]int, lenNums-mid)
    )
    for i := 0; i < lenNums; i++ {
        if i < mid {
            left[i] = nums[i]
        } else {
            right[i-mid] = nums[i]
        }
    }

    return merge(mergeSort(left), mergeSort(right))
}

func merge(left, right []int) (result []int) {
    result = make([]int, len(left)+len(right))

    i := 0
    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result[i] = left[0]
            left = left[1:]
        } else {
            result[i] = right[0]
            right = right[1:]
        }
        i++
    }

    for j := 0; j < len(left); j++ {
        result[i] = left[j]
        i++
    }
    for j := 0; j < len(right); j++ {
        result[i] = right[j]
        i++
    }
    return
}

まとめ

まだまだ、たくさんのアルゴリズムがあるので私自身も色々学習したいと思っております。 アルゴリズムやデータ構造って、へぇーこんなロジックでできているんだなど色々と面白いと思いますので、学習してみてはいかがでしょうか。 データ構造を学習した時の、メモもあるので改良してまた記事として出そうと思います。