クイックソートの基本的な考え方は次のようになります。

まず始めに、「基準値」と呼ばれるデータを決定します。幾つか方法がありますが、今回は配列の中央のデータを基準値とします。基準値を各データと比較し、各データのほうが小さければ、そのデータを配列の前のほうに移動し、大きければ後ろのほうに移動します｡この操作をすべてのデータに対して行うと、配列の前半には基準値より小さいデータが、後半には大きいデータが入ります｡前半のデータ、後半のデータそれぞれで再び基準値を選び、同様の操作を繰り返します｡最終的には操作対象の範囲に入る値が1つになりソートが終了します｡

例として次のような配列Nがあります｡

　　　　　　　　　　　　

この配列Nを配列の中央のデータを基準値としてクイックソートすると次のようになります｡

1では、まず「基準値」を決めます｡今回は 配列の中央のデータを基準値 としています｡
2では、基準値7より小さいデータは配列の前、大きいデータは配列の後ろに移動させています｡
3では、前半の配列、後半の配列でそれぞれの配列の中央のデータを新しい「基準値」を決めます｡
以下同様の処理を繰り返すと、すべてのデータが小さい順に並び変わりソートは終了します｡

Delphiを使ったクイックソートの処理過程を見ることができるプログラムです｡ランダムに作成されたデータをクイックソートを使って、昇順に並べ替えます｡ソートを始めたらソートが終わるまで終了できないので、データの数を多くしすぎたり、処理速度を遅くしすぎると時間がかかるので気をつけてください｡

データ数 データの数を決めます｡ データ作成 視覚的に分かるようにデータを作成します｡データ数を決めてから押してください｡ クイックソート ランダムで作成されたデ-タをクイックソートで整列します｡ 処理速度 処理手順を見るために、わざと処理を遅くしています｡ 数字が大きいほど処理が遅くなります｡

このプログラムを実行したい場合は、下のリンクをクリックして「このプログラムを上記の場所から実行する」を選んでください。
プログラムを実行する

また、バブルソートなどと同じようにデータを棒グラフで表しているクイックソートのプログラムも置いておきます。
プログラムを実行する

クイックソートの基本的な考え方は説明しました。次に、クイックソートのアルゴリズムをDelphiでプログラム化するにはどうすればいいかを説明するために、実際に簡単なプログラムを作ってみます｡

バブルソートのところで作ったプログラムを元にします｡ BubbleButton の Captionを「バブルソート」から「クイックソート」に変え、nameもQuickButtonに変えます。 フォームは次のようになります。
　　

コンポーネント	Name
「データ作成」のボタン	MakeButton
「クイックソート」のボタン	QuickButton
エディット	EditNumber
左のメモ	Memo1
右のメモ	Memo2

「クイックソート」ボタンをクリックしたときのイベントハンドラはバブルソートのままになっています｡そこで、次のもの以外すべて削除してください。


次に、「Quicksort」というモジュールを自分で書きます｡この中にデータをクイックソートするためのプログラムを書いていきます｡

「Quicksort」というモジュールを自分でつくったことを Delphi に知らせるために、コードエディタの上の方で宣言をします。


「クイックソート」ボタンをクリックしたときのイベントハンドラに次のものを付け加えます｡

データをクイックソートするためのプログラムを「Quicksort」に書いてきます｡クイックソートは、配列から基準値となるデータを任意に選びます｡今回は配列の中央のデータを基準値とします｡「Quicksort」に次のようにプログラムを書いてください｡


これで、基準値ｓが決まりました。次は、基準値ｓと各データを比較し、小さければ基準値より前に、大きければ後ろに移動させます｡ 「Quicksort」に次のようにプログラムを書いて、実行してください｡

プログラムを実行すると、基準値ｓよりも小さいデータは基準値ｓよりも前に、基準値ｓよりも大きいデータは基準値ｓよりも後ろに移動しているのが分かります｡

上の実行結果であるソート前の配列N
　　　　　　　　　
を、どのようにして上記のプログラムで基準値ｓと各データを比較し、小さければ基準値より前に、大きければ後ろに移動させたのかをみていきます｡

最初の3行をみると

1行目で、first=1、last=10より　center=5となります。 　2行目は、N[center]=N[5]となるので、s=79になります｡ 　3行目で、N[5]にN[1]を代入します｡

この時点で配列Nは次のようになります｡



次に４行目からfor文とif文の部分までをみていきます｡

4行目は、first=1、なので　ｊ=1となります。 　次のfor文とif文は、 i が2から10になるまで 　N[i]と基準値ｓ を比較して基準値ｓ が大きい場合 　 内の処理を行います｡

このfor文とif文で配列Nが、どのように変わるか見ると次のようになります｡


for文とif文で、最終的に配列Nは
　　　　 　　　となります。


最後に残った部分をみると、次のような処理を行っています｡

first=1、ｊ=5　なのでN[1]にN[5]=75を代入する 　N[5]にs=79を代入する

この処理で配列Nは、次のようになります｡


これで配列Nは、基準値ｓよりも小さいデータは基準値ｓよりも前に、基準値ｓよりも大きいデータは基準値ｓよりも後ろに移動しました｡

上記のプログラムで、基準値ｓと各データを比較し、小さければ基準値より前に、大きければ後ろに移動させるところまではできました。 次にデータがソートされるまで、基準値より前の配列、後ろの配列で、それぞれ再び基準値を選び出し同様の操作を繰り返さなければなりません。これは再帰を用いて表現します｡
「Quicksort」に次のようにプログラムを付け加えてください｡

最後にN[j]に基準値がくるので、前半の配列はN[firat]〜N[j-1]、後半の配列はN[j+1]〜N[last]、ということになります。
Quicksort(first,j-1);で、前半の配列 N[first]〜N[j-1]に対して内の処理を行います｡
Quicksort(j+1,last);　で、後半の配列 N[j+1]〜N[last]に対して内の処理を行います｡

内の処理(「Quicksort」自身の呼び出し)を行うということは、前半の配列でさらに前半・後半にわかれます。後半の配列でも同様です。これらを繰り返していくと、前半の配列なら ｊ-1 の値が first よりも小さくなったり、後半の配列なら ｊ+1 が last よりも大きくなってしまいます｡よって「Quicksort」の繰り返しを止める条件が必要になります｡

基準値を選ぶ必要がない状況として、前半の配列なら first=ｊ-1、後半の配列なら last=j+1 つまり、配列のデータ数が1の時が考えられます｡配列のデータ数が1よりも多い間、「Quicksort」を繰り返せばいいのですから、
if　first＜last　then
を付け加えます｡これで、データ数が1よりも多い間、「Quicksort」を繰り返します。

プログラムを実行すると、データがすべて昇順にソートされています。これでプログラムは完成です｡