13-5. クイックソート
◇クイックソートの原理
クイックソートとは名前の通り速く並べ替えを行うアルゴリズムのことです。
一般的にクイックソートが最も平均的(*1)に速いと呼ばれています。
*1 配列の並び方によって他のソート方法より遅くなることがあります。
(１)
まずは並び替えの方法ですが、最初に配列の中の中間値あたりを基準にします。
理想的なのは最大値と最小値の間くらいの値が望ましいのですが、それは不明であるため、分割等を考慮して配列の中間の値を基準にします。
(２)
次に、その基準値より、小さいものを前に、大きいものを後ろに交換しながら
配列していきます。
(３)
グループ分けが終了した時点で、基準値より手前が２個以上の要素を持って
いた場合、基準値で分割し、その手前の配列で１→３を実行します。
(４)
手前側の配列が無くなったら次は後ろ側の配列に注目し１→４を繰り返します。
このようにグループ分け→分割を繰り返すことによって並び替えを実現します。
この説明だけでは分かりにくいを思いますので、サンプルプログラムの後に一例をいれて置きました。
◇サンプルプログラム１
#include <stdio.h>
#include <string.h>
void qsort(char[], int, int);
void main()
{
char str[256];
int n;
printf("Input: ");
scanf("%s",str);
n = strlen(str);
qsort(str, 0, n - 1);
printf("After: %s\n",str);
return;
}
void qsort(char str[], int first, int last)
{
int i, j;
char x, t;
x = str[(first + last) / 2];
i = first;
j = last;
for(;;i++,j--) {
while (str[i] < x) i++;
while (x < str[j]) j--;
if (i >= j) break;
t = str[i];
str[i] = str[j];
str[j] = t;
}
if (first < i - 1) qsort(str, first , i - 1);
if (j + 1 < last) qsort(str, j + 1, last);
}
◇ソートの例１
C-Production と入力した場合
C-Production (d を基準)
~ ^ ~
C-Pcodurtion (c と r を交換)
~ ^ ~
C-Pcdourtion (o と d を交換)
~^
C-Pcdourtion (交換対象無し)
^
C-Pcd ourtion (左側分割:P を基準:交換対象無し)
^
C- P cd ourtion (左側分割:C を基準)
^
-C P cd ourtion (C と – を交換)
~^
-C P cd ourtion (右側選択:c を基準:交換対象無し)
^
-C P cd ourtion (右側選択:o を基準)
^
-C P cd onrtiou (u と n を交換)
~ ^ ~
-C P cd onroitu (t と o を交換)
~ ^
-C P cd onroitu (交換対象無し)
^
-C P cd onroi tu (左側分割:r を基準)
^
-C P cd onior tu (r と i を交換)
~ ^
-C P cd onior tu (交換対象無し)
^
-C P cd onio r tu (左側分割:n を基準)
^
-C P cd inoo r tu (o と i を交換)
~^~
-C P cd inoo r tu (交換対象無し)
^
-C P cd in oo r tu (右側分割:o を基準)
^
-C P cd in oo r tu (o を交換:実質意味無し)
~^
-C P cd in oo r tu (交換対象無し)
^
-C P cd in oo r tu (右側選択:t を基準)
^
-C P cd in oo r tu (交換対象無し:終了)
^
-CPcdinoortu
◇qsort関数の解説
前回、製作しましたqsort関数を解説します。
理論どおり再帰を使った関数なので、ちょっと難しいかもしれませんが前回のソート例を見ながら追いかけてみてください。
1:void qsort(char str[], int first, int last)
2:{
3: int i, j;
4: char x, t;
5:
6: x = str[(first + last) / 2];
7: i = first;
8: j = last;
9: for(;;i++,j--) {
10: while (str[i] < x) i++;
11: while (x < str[j]) j--;
12: if (i >= j) break;
13: t = str[i];
14: str[i] = str[j];
15: str[j] = t;
16: }
17: if (first < i - 1) qsort(str, first , i - 1);
18: if (j + 1 < last) qsort(str, j + 1, last);
19:}
１：関数の定義の開始
str[] ソートの対象にする文字列
first 文字列の先頭の要素番号
last 文字列の最後の要素番号
３～４：変数の宣言
i 基準より手前側の要素の位置
j 基準より後ろ側の要素の位置
x 基準値(文字)
t 値交換用の変数(Tempのt)
６：基準値の決定
対象となる文字列の中間点の文字を基準値にします
７～８：前方・後方それぞれの開始点をセット
９～１５：クイックソート
前方・後方より基準値と比較して交換対象になる値を探し、
最初に見つかった場所通しで交換をします。
交換が終わったら、開始点を一つ中央に寄せて繰り返します。
１７：前方部分の分割
９～１５で交換が出来なくたったとき、基準値の前方の配列が２つ以上の
要素を持っていれば、分割し前方の配列のみでクイックソートを行います。
１８：後方部分のクイックソート
１７でクイックソートが完了したら、残りの後方部分をソートします
１９：関数の終わり
これを再帰的に繰り返すことによって、最終的にソートが完了します
◇スタック方式のアルゴリズム
クイックソートのアルゴリズム自体は再帰を使いますが、再帰の代わりにスタックを用いて実現することができます。
再帰を使わずスタックを用いる理由としては、まず再帰が使えない言語でも利用できるということ、そして再帰では実行時間やメモリーを大量に消費する場合が考えられます。
ところでスタックとは何でしょう？
『逆ポーランド記法』でスタックについて解説されることが多いようですがついでなのでここで簡単に説明します。
スタックとはイメージとしてブロックの積み上げのようなものです。
入出力の種別ではＦＩＬＯ(*1)と呼ばれ。最初に入ったデータが最後に出る形式の配列を意味します。
それに対して、入力した順番にデータが出されるものをバッファと呼び、ＦＩＦＯ(*2)形式になっています。イメージとしてはトンネルです。
説明はここまでで、以下は簡単に図を描いて見ます。
スタック
┌────┐
↑│データ４││読
読│├────┤│み
み││データ３││込
込│├────┤│む
む││データ２││順 下から順に書き込んで行き
順│├────┤│番 最後に書き込んだデータから
番││データ１│↓ 順番に下に向かって読み込む
───┴────┴───────────────────────────
これをプログラムで実現する為には、配列やポインタでデータを書き込む度に、要素番号をインクリメントし、
読み込んだときは要素番号をデクリメントします。
ただし、スタックに使用する容量に十分気をつけないとスタックオーバーを起こしたとき、プログラムが停止する可能性があります。
*1 FILO (First In Last Out) … 先入れ後出し。スタックの方式
*2 FIFO (First In First Out) … 先入れ先出し。バッファの方式
◇サンプルプログラム２
それでは、前に出てきたクイックソートプログラムを、スタック仕様で書き換えてみました。配列の分割部分だけ変わっています。
#include <stdio.h>
#include <string.h>
void qsort(char[], int, int);
void main()
{
char str[256];
int n;
printf("Input: ");
scanf("%s",str);
n = strlen(str);
qsort(str, 0, n - 1);
printf("After: %s\n",str);
return;
}
void qsort(char str[], int first, int last)
{
int i, j,p=0;
char x, t;
int stack_first[256];
int stack_last[256];
while(1){
x = str[(first + last) / 2];
i = first;
j = last;
for(;;i++,j--) {
while (str[i] < x) i++;
while (x < str[j]) j--;
if (i >= j) break;
t = str[i];
str[i] = str[j];
str[j] = t;
}
if (first < i - 1){
stack_first[p] = i;
stack_last[p] = last;
p++;
last = i - 1;
continue;
}
if (j + 1 < last){
first = j + 1;
continue;
}
else {
p--;
if(p<0)return;
first = stack_first[p];
last = stack_last[p];
continue;
}
}
}
本講座は以上で終了です。おつかれさまでした。