C言語 クイックソートについて

質問

クイックソートでわからない点があるため、
質問させていただきます。

-----------------------------------------------------
～省略～
data = [5, 3, 4, 2, 6, 1];
no = 6; //データの個数
～省略～
dqsort(data, 0, no-1);
～省略～

void dqsort(double data[], int lower, int upper) {
　　int i, boundary; //boundaryは配列の前半と後半の境界を示す

　　if(lower >= upper) { return; }
　　//基準値となる値（データの中央に位置する値）とデータの先頭の値を入れ替える
　　swapdata(&data[lower], &data[(lower + upper)/2]);
　　boundary = lower; //boundaryを先頭に移動させる
　　　　for(i=lower+1; i<=upper; i++) {
　　　　　　if(data[i] < data[lower]) {
　　　　　　　　//配列の前半部分に移動し、境界を移動する
　　　　　　　　swapdata(&data[++boundary], &data[i]);
　　　　　　}
　　　　}
　　//最後に基準値を境界位置にコピー
　　swapdata(&data[lower], &data[boundary]);
　　//配列の前半部分をクイックソート
　　dqsort(data, lower, boundary-1);
　　//配列の後半部分をクイックソート
　　dqsort(data, boundary+1, upper);
}

void swapdata(double *i, double *j) {
　　int temp;

　　temp = *i;
　　*i = *j;
　　*j = temp;
}

---------------------------------------------------------

基準値と配列の先頭のデータを入れ替えた後、
データは、[4, 3, 5, 2, 6, 1]となり、lower = 0であるため、
data[boundary]はdata[0]となります。
for文の最初のループでdata[0]<data[1]なら、
swapdata(&data[++boundary], &data[i]);
となっているのですが、
[++boundary]の部分はboundary=0に1を足してから処理するため、
swapdata(&data[1], &data[1]);
となると思うのですが、そうすると同じデータを入れ替えることになってしまいます。
何が間違っているのか、教えていただけますでしょうか。

回答No.3

Lchan0211b · ベストアンサー

何も間違ってないと思います。

> swapdata(&data[1], &data[1]);
> となると思うのですが、そうすると同じデータを入れ替えることになってしまいます。

ここは、たまたま境界の右隣のデータを入れ替える時には
境界をずらした結果、無駄に同じ場所を入れ替えることになりますが、
それで意図しない結果が生じるわけではありません。
実際に動かして検証したわけではありませんが、おそらく
このコーディングで正しくソートできると思います。

重いものを入れ替えるなら、入れ替えようとしているデータが
既に境界の左に入っているかどうかチェックする処理を入れた方が
よいかもしれませんが、そのチェック処理が1stepであっても、
データ数が多くてたくさん入れ替えるならその数分のstepが増えます。
たった6個のデータの並べ替えではなく、もっとたくさんのデータの
並べ替えをする場合、たまたま境界の右隣を入れ替えるケースは
少ないですから、毎回入れ替える前にそのチェックをする方が
コストがかかる可能性が高いです。
(そもそも重いものを直接移動して並べ替えてはいけませんよね。
重いものを並べ替えたいなら、その重いものにインデックスを
付与し、インデックスを並べ替えてインデックス経由でアクセス
するべきですよね。)

なお、クイックソートは、基準値の左右にデータを分けて行くという
考え方で、その分ける方法の違いは、本質的な違いではないと思います。
例えば
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
は、左右の両方から基準値に反するデータを探して入れ替えるように
していますし、
http://www.daccho-it.com/program/algo/quick.htm
は、質問にあるのと同じような方法で左から順番にチェックして入れ替えて
いますが、一番左のデータを基準値として処理しています。

お礼

回答ありがとうございます。

>swapdata(&data[1], &data[1]);
この部分で同じデータを入れ替えることになるのは正しいのですね。

boundaryの使い方がよくわかっていなかったのですが、
基準値と配列の先頭のデータを入れ替えた後の配列が[4, 3, 5, 2, 6, 1]となっている場合、
for文の1回目のループでdata[1]=3の位置にboundaryがあり、
2回目のループではboundaryの位置は変わらず、
3回目のループでboundaryはdata[2]の位置に移動し、
data[2]とdata[3]の値を入れ替えるということなのですね。
（データは[4, 3, 2, 5, 6, 1]となり、boundaryはdata[2]の位置にある）

>重いものを入れ替えるなら、入れ替えようとしているデータが
>既に境界の左に入っているかどうかチェックする処理を入れた方が・・・
のところで、重いものというのは大きい値という意味ですよね？

>データ数が多くてたくさん入れ替えるならその数分のstepが増えます。
>たった6個のデータの並べ替えではなく、もっとたくさんのデータの
並べ替えをする場合、・・・毎回入れ替える前にそのチェックをする方が
コストがかかる可能性が高いです。
この部分をもう少し詳しく教えていただけますでしょうか。
クイックソートでは時間がかかりすぎるということでしょうか。

回答No.7

akayoroshi

#2の回答を寄せたものです
> カーニハン・リッチーの「プログラミング言語C」にも出てきます。
ということで、検索したら参考URLに示したe-Book（PDFファイル）がありました。
この74ページ、再帰のサンプルとして、質問中のプログラムと同じものがありました。（変数名と型が違うだけでコーディングは全く同じです。）

参考URL：

http://www.iups.org/media/meeting_minutes/C.pdf

お礼

回答ありがとうございます。

お礼が遅くなって申し訳ありません。
わざわざ調べていただき、ありがとうございました。
クイックソート以外にもコードがたくさん載っていて、
大変勉強になります。
何度も回答いただき、ありがとうございました。

回答No.6

Wap58

とてもユニークなソート関数です

forを２回呼んで配列要素の衝突もないし

swap関数が無駄に入れ替えしてます

でも、皆さんの解答で解決済みだと思います

考え方の違うソートはたくさんあるので

ネットなどで検索されて効率的なソースを

色々試して実行速度を調べて下さい

こんなソースで乱数ファイル作れば検証しやすいです

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void){
int i,ran;
FILE *fp;
char *name = "DATA.txt";
srand(time(NULL));
fp = fopen(name,"w");
for(i=0;i<500000;i++){
ran = (int)((rand()*100000.0)/(RAND_MAX*1.0));
fprintf(fp,"%d",ran);
fprintf(fp," ");
}//END for
fclose(fp);
return 0;
}

ループも仕様って書いていいのか分かりませんけど
Winだと;で添字を進めるで問題ありません
Macだと{}じゃないとエラーになります

for( ; data[left] < separator; left++);
for( ; separator < data[right]; right--){}

お礼

回答ありがとうございます。

クイックソートはデータの両端から基準値と比較していく方法しか知らなかったため、
今回別のソートの方法を知り、大変勉強になりました。

乱数ファイル作成のコードを記述していただき、ありがとうございます。
他のソースコードでも実行速度を試してみたいと思います。
あと、ループ処理を行う文（for文など）で何も処理を行わない場合は、
Macだと{}をつけなければいけないのですね。
教えていただき、ありがとうございます。

回答No.5

Lchan0211b

No.3です。

お礼の追加質問に回答します。

>>重いものを入れ替えるなら、入れ替えようとしているデータが
>>既に境界の左に入っているかどうかチェックする処理を入れた方が・・・
> のところで、重いものというのは大きい値という意味ですよね？

大きい値というよりも、構造体配列のように配列の1エントリの
サイズが大きいデータを入れ替える場合という意味です。
1エントリ256バイトの配列エントリの入れ替えをしようとしたら、
256バイト×3回のコピー処理が必要になりますから。
「インデックスを付与する」も抽象的に書きましたが、
構造体配列の話で言えば、構造体配列のエントリを移動して
入れ替えるのではなく、各構造体エントリをポイントする
ポインタの配列を作り、そのポインタ配列をソートすべき
ということです。

> 並べ替えをする場合、・・・毎回入れ替える前にそのチェックをする方が
> コストがかかる可能性が高いです。
> この部分をもう少し詳しく教えていただけますでしょうか。

今回の質問にある無駄処理を省こうとして、
例えば
swapdata(&data[++boundary], &data[i]);
の処理を単純に
------------------------------------
boundary++;
if (i > boundary) {
swapdata(&data[boundary], &data[i]);
}
------------------------------------
と必要な時だけswapdataの呼び出しをやるようにすると、
むしろ性能劣化になる可能性が高いですよということです。

例えば10万回のデータの入れ替えが必要なケースで
(i > boundary)のチェック処理をすることで1000回の無駄な
swapdata呼び出しが抑えられたとしても、残り9万9千回の
入れ替え処理は無駄なチェックになっているので、
その9万9千stepも費やしているチェック処理を省略した方が性能が
よいということです。

ちなみに、No.2,4さんが書かれている方法ならちゃんと性能改善に
なります。
この方法は先に無駄部分のチェックをして、チェックを済ませた
後(boundary以降)から入れ替え処理を開始しているため、
無駄部分のチェックは悪い影響を及ぼしません。

ついでにNo.4さんのお礼に書かれている質問に少しだけコメントすると、
whileの条件文の最後に「;」が着いているのは誤りではありません。
whileの中にforがあるのではなくwhileでboundaryを適切な位置まで
歩進させた後、改めてboundary位置からfor文を開始する設計だと
思います。

お礼

再度回答ありがとうございます。

重いものというのはサイズの大きいデータのことで、
さらに、その配列データ自体を入れ替えるのではなく、
ポインタを使って入れ替えたほうがいいのですね。
また、同じデータを入れ替えるのを防ぐために、
各データについて(i > boundary)のようなチェックをいれると、
結局無駄に処理することになるのですね。
大変わかりやすい説明をしていただき、ありがとうございました。

あと、#4さんの御礼コメントで質問したwhile文の件についても
教えていただき、ありがとうございました。
配列のデータが[4, 3, 5, 2, 6, 1]となっているとき、
while文でboundaryをdata[2] = 5の位置まで進めた後、
for文でdata[boundary](＝data[2])とdata[3]の入れ替えを行うという意味なのですね。

回答No.4

akayoroshi

#2です
コメントの説明が逆でした。あといくつか修正します
boundary = lower; //boundaryを先頭に移動させる
while( ++boundary<=upper && data[boundary]<=data[lower] ) ; // 列の頭にある、基準値よりも小さなデータはそのままにしておく
for(i=boundary--; i<=upper; i++) {　// boundaryはインクリメント済みなのであとの処理とのつじつま合わせのために元に戻しておく

お礼

回答ありがとうございます。

元のデータが[5, 3, 4, 2, 6, 1]の場合、基準値と先頭のデータを入れ替えて、
[4, 3, 5, 2, 6, 1]となっているとすると、

>while( ++boundary<=upper && data[boundary]<=data[lower] ) ;
>// 列の頭にある、基準値よりも小さなデータはそのままにしておく
whileの条件文の最後に「;」がついていますが、
これは↓のように実際はwhile文の中にfor文が含まれるということでよろしいでしょうか。
while( ++boundary<=upper && data[boundary]<=data[lower] ) {
　　for(i=boundary--; i<=upper; i++) {
　　～省略～
　　}
}
//最後に基準値を境界位置にコピー
swapdata(&data[lower], &data[boundary]);
～省略～

この部分で、2回目のループで
while(2 <= upper && data[2] <= data[0]);
となり、data[2]=5、data[0] =4となるため、
for文は実行されないことになってしまうのですが、
この点について教えていただけますでしょうか。

補足

#5さんに教えていただき、
while( ++boundary<=upper && data[boundary]<=data[lower] ) ;
は、
配列のデータが[4, 3, 5, 2, 6, 1]となっているとき、
while文でboundaryをdata[2] = 5の位置まで進めるということなのですね。
while文を実行した後、data[2]とdata[3] = 2を入れ替えるため、
for文を実行するという意味だったのですね。
（つまり、while文にfor文が含まれているわけではない）
以下の御礼コメントの質問を訂正させていただきます。
すみません。

回答No.2

akayoroshi

もともとのデータが、[5, 3, 6, 2, 4, 1]　だったら、基準値が6になります。このときは、基準値以外の全部の要素について同じデータの入れ替えがおきます。
これを防ぎたいのなら、
boundary = lower; //boundaryを先頭に移動させる
while( boundary<upper && data[lower]>=data[++boundary] ) ; // 列の頭にある、基準値よりも大きなデータをスキップする
for(i=boundary+1; i<=upper; i++) {
のようにすれば効率を落とすことなく余計な交換をなくすことができます。

このプログラムで使っている分割のアルゴリズムは、基準値よりも小さな値を見つけてそれを列の先頭から順番に詰めていくというものです。カーニハン・リッチーの「プログラミング言語C」にも出てきます。

お礼

回答ありがとうございます。

御礼コメントは#4のほうに書かせていただきます。

回答No.1

hashioogi

どこが間違っているかを指摘する以前に、果たしてこれはクイックソートなんでしょうか？

少なくとも、
クイックソートなら基準値未満かどうかを下から上に向かって調べるfor文と、基準値以上かどうかを上から下に向かって調べるfor文の2つがあるはずだと思うんですけど。

お礼

回答ありがとうございます。

基準値を設定し、基準値よりも大きいグループと小さいグループに分けて、
さらにそれぞれをソートしているため、クイックソートとなっていると思います。