【ソートアルゴリズム２】クイックソート [WIP]

クイックソートとはなんぞや

バブルソートより早いアルゴリズム。 配列の中から適当なIndexの値を取得して、その値を基準に配列を２つにぶった切る。 で、配列の前半と後半でそれぞれソートをかける。また、再帰関数的にそれを繰り返す。

クイックソートは複雑

再帰関数を使って理解しようとすると頭が混乱していくので、3つのパートに分けて考える。

その1: main()からソート用の配列をコール

任意の数を取得する。与えられた配列の中身がぐちゃぐちゃになっていることを前提にしているので、配列のインデックス0を取得する。

   p := param{5, 10, 30, 27, 4, 0, 2, 13, 17, 8, 20, 23, 26}

    // 基準となるインデックス0、配列の長さ、配列自体を引数として渡す。
    // QuickSort()はこれから定義するので一旦無視でOK
    result := p.QuickSort(0, len(p)-1, p)

その2: 値を大雑把に移動していく

基準より小さい数は前側に、基準より大きい数は後ろ側に集めていく。

func (p param) QuickSort(low, high int, param param) []int {
    if low >= high {
        return param
    }

    start := low
    max := high

    // 基準にする値を先頭の値とする
    pick := param[low]

    for low < high {
        // 基準値より大きい値を前から検索
        for low <= high && param[low] <= pick {
            low++
        }
        // 基準値より小さい値を後ろから検索
        for low <= high && param[high] > pick {
            high--
        }

        // 値の入れ替え
        if low < high {
            p[low], p[high] = p[high], p[low]
        }
    }

    // 基準値を中央に移動
    p[start], p[high] = p[high], p[start]
}

ここまでで、元の配列[5, 10, 30, 27, 4, 0, 2, 13, 17, 8, 20, 23, 26] から[4 2 0 5 27 30 10 13 17 8 20 23 26]に変わる。 基準値の5よりも小さい数が前の方に集まってきている。

その3: 配列の前半部分を更にソートする

再帰的にQuickSort()を呼び出すことで、配列の最初〜基準値までをソートする。

   // 再帰的呼び出し
    // index:0 〜 基準値の一個したまでをソートする。
    p.QuickSort(start, high-1, p)

ちなみに、QuickSort()の最初で定義しているif low >= high {}を忘れると、無限ループになって落ちる。

func (p param) QuickSort(low, high int, param param) []int {
    // これの書き忘れに注意
    if low >= high {
        return param
    }