クイックソート

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

アルゴリズム概要

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

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

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

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

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

6. plとprが交差していなければ、2へ戻る

交差していれば、

・範囲の左端からprまでの範囲を対象に同じことを繰り返す

・plから範囲の右端までの範囲を対象に同じことを繰り返す

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

枢軸の求め方

枢軸の求め方については、いろいろな方法があります。

    • 配列の先頭
    • 配列の中間 ← 教科書のやり方
    • 配 列の末尾
    • 上記3つの中の中央値をとる

サンプルプログラム

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