クイックソート

ソートアルゴリズムの最後を飾るのは、やはりクリックソートです。 クイックソートは、データの比較と交換回数が非常に少ないのが特徴で、一般的なばらばらデータ（ランダムに散らばっているデータ）に対して、最も効率良く並べ替えを実行します。 クイックソートは、実用上もっとも高速であるとされている並べ替えアルゴリズムで、多くのプログラムで利用されています。 ばらばらなデータが格納された配列 a[ ] が与えられた場合に、それらをクイックソートで並べ替える手順を、下の図に示します。 まず始めに、「軸要素」と呼ばれるデータ値を決定します。この値は、データ全体を2つに分割するときのしきい値として使われます。軸要素は、分割が均等に行われるように選ぶのが望ましいのですが、その選択に時間をかけると、かえって並べ替えの時間を大きくしてしまいます。一般には、次のような方法がよく用いられているようです。 データの先頭の

[keisei_1092]

#情報科学の基礎

[witt]

O(N^2)。分割がアンバランスになる最悪の場合の話。