クイックソート
読み：クイックソート
外語：quick sort
ソートアルゴリズムの一つ。
数列をある数値T(数列の中に含まれている数値なら何でもよい)より小さな数値の部分数列、Tと同じ数値の部分数列、Tより大きな数値の部分数列の3つに分割することを繰り返して実現されるソート。
最悪計算量はO(n^2)であり、これだけを見るとアルゴリズムとしてはよくないように見える。しかし、平均計算量はO(n log n)であり、また実際にソートを行なうと他のどのソートよりも早く処理を行なうことができる。そのためクイックソートという名がつけられている。
現在使われているソートアルゴリズムはほぼクイックソートであるが、数列の並び方によっては計算量が大きくなってしまう欠点がある。そのため標準C++ライブラリでもクイックソート、ヒープソート、マージソートの3種類が用意されている。
クイックソートの途中経過
5 8 6 1 7 11 5 3 初期状態 → 分割するときに利用する
数値(基準値)を7とする
5 6 1 5 3 | 7 | 8 11 1回目 → 1つめの部分数列の基準値
を5, 3つめは8とする
1 3 / 5 5 / 6 | 7 | 8 / 11 2回目 → 1つめの基準値を1とする
(他の部分はソート終了)
1 . 3 / 5 5 / 6 | 7 | 8 / 11 3回目(終了)
再検索