クイックソート

最速のソートアルゴリズムの1つです.

アルゴリズム概要

1.真ん中の位置の数を枢軸とする

2.範囲の左端から枢軸以上の位置を探す  pl

3.範囲の右 端から枢軸以下の位置を探す  pr

4.もし、plとprが交わっていなければ、plの数とprの数を交換する

5. そのあと、plを1つ右に移動、prを1つ左に移動

6.    plとprが交差していなければ、2へ戻る
                       交差していれば、
         ・範囲の左端からprまでの範囲を対象に同じことを繰り返す
          ・plから範囲の右端までの範囲を対象に同じことを繰り返す

というように2つのグループに分けて再帰的に処 理を行います.再度同じ処理を繰り返すことで,最終的にソーティングされます.

枢軸の求め方

枢軸の求め方については、いろいろな方法があります。
  • 配列の先頭
  • 配列の中間 ← 教科書のやり方
  • 配 列の末尾
  • 上記3つの中の中央値をとる 


サンプルプログラム
教科書のプログラムを元にしたコマンドラインプログラムですが、挙動を確認するには利用してください。

Comments