●クイックソートは世の中で最も速いソートアルゴリズムとして知られています。（これは、一つのＣＰＵで順次処理を行なった場合である。最近では、計算機の機能が高まり、並列処理や分散処理が可能となっているため、複数のＣＰＵを持った計算機上での並べ換えについては、クイックソートよりも速いアルゴリズムが提案されている。）
●クイックソートは、データを分割してより小さな単位でソートし、あとであわせるという手法をつかって効率を上げています。つまり、
１ データのブロック分割
２ 各ブロックごとの処理（並べ換え）
３ ブロックの統合
という順に作業がすすめられるわけです。速くなるかどうかは１のデータの分割の仕方が工夫のしどころでいろいろなやり方が提案されています。ここで取り上げるのはその中の１つです。。
●次のような数字で実際にやってみます。
（１）まず与えられたデータ列の真ん中（左から６番目）に位置する データを基準値として定めます。例では、３５を基準値とします。
52 46 24 12 15 35 18 56 63 23
（２）データを左から順に基準値よりも大きいデータを捜します。まず５２が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 ２３が見つかります。
52 46 24 12 15 35 18 56 63 23
（３）ここで、５２と２３を入れ替えます。現在注目しているデータの位置を次に進めます（左から見ている場合は一つ右へ、右からの場合は左へ一つ進める）。
23 46 24 12 15 35 18 56 63 52
（４）引き続き左から順に基準値よりも大きいデータを捜します。続きは４６から始まるがすぐ４６が見つかります。続いて、右から順に基準値よりも小さいデータを捜します。 １８が見つかります。
23 46 24 12 15 35 18 56 63 52
（５）４６と１８を交換します。
23 18 24 12 15 35 46 56 63 52
（６）続けて左から基準値より大きいデータを探します。基準値に等しい場合も取り上げることにすると３５そのものに合います。右からも同様に小さいものを探すと３５に合います。これで左右からの捜索がぶつかりました。
ぶつかった所より左は基準値より小さなものが、右は大きいものが集まっています。
23 18 24 12 15 35 46 56 63 52
ここで、２つの部分に分けて、それぞれ（１）からと同様に作業をしていきます。
（７）前半分は１番から５番までです。データ列の真ん中（左から３番目）に位置するデータを基準値として定めます。例では、２４になります。以下同様なのですが、今回は基準値が、たまたまその範囲の最高値になっているのでちょっと面倒です。こんなときでもうまくいきます。
23 18 24 12 15 35 46 56 63 52
（８）データを左から順に基準値(24)よりも大きいデータを捜します。２４です。続いて、右から順に基準値よりも小さいデータを捜します。 １５です。
23 18 24 12 15 35 46 56 63 52
（９）２４と１５を交換します。
23 18 15 12 24 35 46 56 63 52
（10）続けて左側から基準値より大きいものを探します。さっきは２４が３番にありました。今度は４番から探します。すると５番の２４が見つかります。右側からは、基準値より小さいものを探します。さっきは５番に１５がありましたから今度は４番から始めます。すぐ１２が小さいということになります。
23 18 15 12 24 35 46 56 63 52
（11）これで左右からの捜索がぶつかりました。左から来たのは５番の２４まで来ましたし、右からのは４番の１２まできましたから、交差して行き過ぎています。このようなときは交換せず、４番と５番の間でデータを２つに分けます。基準値であった２４よりも小さいものと大きいものに分かれます。右側の２４より大きいのは１つしかありませんが、たまたまこの範囲の最大値だったので仕方ありません。一つしかない要素はこのまま位置が確定します。
23 18 15 12 24 35 46 56 63 52
（12）分かれた１番から４番に対してふたたび(１)からのように、作業をします。繰り返すうち、要素が１つ部分ができては確定してゆきます。前半が終われば後半に進み、ついには全部整列されます。
●ある基準値を決めて、それより大きいか小さいかで２つに分け、分かれたものについても同じことを繰り返す。ということです。基準値はデータの大きさで真ん中あたりの数であれば都合がいいのですが、それをじっくり選んでいると時間がかかるので位置で真ん中のものを「えいっ」とつかんで採用するわけです。
●原理的にはここまでなのですが、実際にプログラムを組むときには分けるときの境界を含めるか含めないかで迷います。=< を使うか、< を使うかを間違えると、うまく働かないこともありますからじっくり考えなければならないことになります。
●前と同じです。乱数でつくる方を使いましょう。
RANDOMIZE INPUT n DIM a(n) FOR i=1 TO n LET a(i)=INT(RND*1000) NEXT i
●この繰り返しは、単純ではありません。たしかにａ番目からｂ番目までを基準値に従って２つに分けるという作業が繰り返されいますが、２つに分けたその両方をさらに２つに分けると、いうところで行き詰まります。
●ここで新しい手法を使います。それは再帰と呼ばれます。
●まず、「ａ番目からｂ番目までを基準値に従って２つに分ける」という作業を副プログラム（サブルーチン）として独立させます。データとａ，ｂを与えてこの副プログラムを呼び出すと、データを２つに分けてくれる様にするということです。データを用意して作業員に「こっちへ来てやってくれ」と呼び出すという感覚から、副プログラムは「呼び出す」といいます。
●この教科書では初めてですが、副プログラムの使用はそう難しくありません。問題は次です。この副プログラムの中で、自分自身を呼び出す様にするのです。（十進BASICではこれが可能です。システムによってはできません）この「副プログラムの中で、自分自身を呼び出す」ことを「再帰呼び出し」といいます。
●再帰は考え方としては難しいのですが、とても強力な見方です。今回の例でいえば、「ａ番目からｂ番目までを基準値に従って２つに分ける」という副プログラムの最後に、２つに分けた部分をさらに２つに分けるように自分自身を呼びだす部分をつくっておけばよいのです。そうすれば２つに分けるたびに、新たにできた２つもさらに２つに分けられて、ついに１つづつになったときには整列が完成しているということになります。ドミノ倒しの様に最初の１つだけかけば後は全部自動的に終わってしまいます。という訳で整列の本体部分はこれだけです。
LET t0=TIME
CALL sort(a,1,n)
LET t1=TIME
●t0=TIME などは時間を計るためのものですから、本体は本当は１行で終わりです。sort は「ａ番目からｂ番目までを基準値に従って２つに分ける」という副プログラムの名前で、変数の名前のように自分で決めます。後ろの（ ）内は引数といって副プログラムに渡すデータです。a( ) の配列全部と、最初の番号と最後の番号です。はじめは１からｎまでになります。副プログラムの内容は後で説明します。
●注意 これまでは後で説明する内容で色つきの部分が書き換えて完成でしたが、今回は違います。この部分は本当にこれで完成です。
●結果表示はやはり１０００件以下の時だけ結果を表示する様にします。かかった時間だけはいつも表示します。
IF n < 1000 THEN
FOR i=1 TO n
PRINT a(i);
NEXT i
PRINT
END IF
PRINT t1-t0;"秒"
●主プログラムと副プログラムの関係を説明します。（主プログラムと副プログラムはプログラマの間では普通メインルーチン、サブルーチンといいます）緑の部分が主プログラム、青の部分が副プログラムです。
DECLARE EXTERNAL SUB sort !使用する副プログラムの宣言（sort を使うぞ！） 配列の用意 CALL sort(a,1,n) !ここで副プログラムを呼び出す 整列した結果の表示 END !ここが主プログラムの終わり。忘れずにここにENDを書く。 EXTERNAL SUB sort(a(),sml,big) !副プログラム本体の始まり(これがsortだ！) sml番目からbig番目までを基準値に従って２つに分け、 前半を指定して再帰呼び出しをする……CALL sort(a,sml,bg) 後半を指定して再帰呼び出しをする……CALL sort(a,sm,big) END SUB !ここが副プログラムの終わり。
●副プログラムは EXTERNAL SUB 名前(引数)という行で始まり、END SUB で終わります。副プログラムは同じような処理が何度も出てくるときに使いますが、今回は再帰呼び出しで使っているので、副プログラム中にも CALL があります。
EXTERNAL SUB sort(a(),sml,big) !副プログラム本体の始まり(これがsortだ！) LET sm=sml LET bg=big LET x=ROUND((sm+bg)/2,0) LET kjn=a(x) !これが基準値 DO DO WHILE a(sm) < kjn !左から大きいものを検索 LET sm=sm+1 LOOP DO WHILE kjn < a(bg) !右から小さいものを検索 LET bg=bg-1 LOOP IF sm =< bg THEN !交換して先に進む LET t=a(sm) LET a(sm)=a(bg) LET a(bg)=t LET sm=sm+1 LET bg=bg-1 END IF LOOP WHILE sm =< bg IF sml < bg THEN CALL sort(a,sml,bg) !前半を指定して再帰呼び出し IF sm < big THEN CALL sort(a,sm,big) !後半を指定して再帰呼び出し END SUB !ここが副プログラムの終わり。
●上記プログラムを完成させ、時間をはかりなさい。
●time.txtに追加記入してBASIC内に提出
| 方式 | 1000個 | 2000個 | 10000個 |
| 選択ソート | x.xx | xx.x | xxx.x |
| バブルソート | x.xx | xx.x | xxx.x |
| クイックソート | x.xx | xx.x | xxx.x |