【Go言語でソートアルゴリズムを学ぶ】クイックソート

クイックソートとは

目印となる基準値を決定して、基準値より大きいかそれ以下のグループに分けます。さらに、分割されたグループでも同様に基準値を決定して基準値より大きいかそれ以下のグループ分けを実行していきます（再帰処理）。最終的に分割できなくなるまで実施します。

平均的な計算量は O(nlogn)です。 ただし、基準値の決定方法によって計算量がO(n^2)になってしまうので注意が必要です。 そのため、基準値をランダムに選択したり中央値を選択するなどの方法があります。

Go言語でのコード例は以下の通りです。

Embedded content: https://gist.github.com/sena-anny/320a0f1931132adea4d0a46155c65f46

数字の配列の先頭を基準値として基準値より大きいグループと基準値以下のグループに分割します。

分割された配列で先頭を基準値として基準値より大きいグループと基準値以下のグループに分割します。

分割できなくなるまで実行します。

例）初期状態: [2, 1, 5, 4, 3]

1回目：　　配列の先頭の2を基準値に[1]（分割できないので終了）と [5, 4, 3]にグループ分けします。

2回目：　　配列の先頭5を基準に[4, 3]と[]（分割できないので終了）にグループ分けします。

3回目: 　配列の先頭4を基準に[3]と[]（分割できないので終了）にグループ分けします。

以上から[1, 2, 3, 4, 5]に並べ替えられます。