クイックソート

ソートアルゴリズムの一つ。

数列をある数値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回目(終了)

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)