アルゴリズムとデータ構造 - マージソート

アルゴリズム データ構造 マージソート

プログラミング

2020-02-01 16:02:11

概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

マージソート

  • データ列が分割できなくなるまで(要素が1つ)再帰的に分割を行い、分割されたデータを複数回マージを繰り返していくことによってソートする
  • 分割統治法に基づくソート
    • 大きな問題を小さな問題に分割する

計算時間

  • 最悪計算時間
    • O(n log n)

実装

// cf. https://github.com/TheAlgorithms/Go/blob/master/sorts/merge_sort.go
package main

func merge(a []int, b []int) []int {
    r := make([]int, len(a)+len(b))
    i := 0
    j := 0

    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            r[i+j] = a[i]
            i++
        } else {
            r[i+j] = b[j]
            j++
        }
    }

    for i < len(a) {
        r[i+j] = a[i]
        i++
    }

    for j < len(b) {
        r[i+j] = b[j]
        j++
    }

    return r
}

func mergeSort(n []int) []int {
    if len(n) < 2 {
        return n
    }

    var middle = len(n) / 2
    a := mergeSort(n[:middle])
    b := mergeSort(n[middle:])
    return merge(a, b)
}

参考

About the author

Image

bmf san @bmf_san
A web developer in Japan.