ページ 1 ／ 1
クイックソートについて質問
Posted: 2007年12月18日(火) 11:00
by parapara
本に以下のように書いてありました。
実際に正しく動きます。ですが、下記のような疑問が沸きました。
#include<stdio.h>
void quick(int *,int ,int);
#define N 10
int main(void){
static int a[/url]={41,24,76,11,45,64,21,69,19,36};
int k;
quick(a,0,N-1);
for(k=0;k<N;k++){
printf("%4d",a[k]);
}
puts("");
return(0);
}
void quick(int *a,int hajime,int owari){
int jiku=hajime,i=hajime,j=owari+1;
int temp;
if(hajime>=owari)return;
while(1){
while(a[++i]<a[jik[/url]);//************************
while(a[--j]>a[jik[/url]);//************************
if(i>=j)break;
temp=a;
a=a[j];
a[j]=temp;
}
temp=a[jik[/url];
a[jik[/url]=a[j];
a[j]=temp;
quick(a,hajime,j-1);
quick(a,j+1,owari);
}
*印の所でjが負の値に成ってしまったり、iがowariを超えることは無いんでしょうか？。
Re:クイックソートについて質問
Posted: 2007年12月18日(火) 13:11
by 管理人
クイックソートは左から調べているiの値と右から調べているjの値がぶつかったらそこで探索は終了するので、owariを越える事はありません。
「ピポッド以上を探索、ピポッド以下を探索」するということは、探索範囲で少なくともピポッド自身で一回とまるはずです。
どこにも探索がヒットしなければ、少なくともお互いが探索時にピポッドでとまるはずですから、
ぶつかったことが判定出来ます。
・・と言ってもわかりにくいので、動的な解説つきで見てもらったほうが解りやすいと思いますので、
http://dixq.net/sort.html
よかったら、クイックソートの解説用アプリを作っておりますので、こちらで確認してください。
Re:クイックソートについて質問
Posted: 2007年12月18日(火) 13:23
by parapara
Dixq様ありがとうございます。アプリもみて再度考えて見ます。
Re:クイックソートについて質問
Posted: 2007年12月18日(火) 14:04
by parapara
アプリ見てみました。凄くよく分かったのですが、一回勉強してみて、つまづいた人が見るのが、
最も効果的だと思いました。本で言うところのポインタ完全制覇ｗｗｗ。
そして本に書いてあったクイックソートの基本を知るための基本の上記プログラム
ピボットを常に調べる部分配列の先頭にする上記プログラム
ではiがowariを超えることはありそうです。
たまたま、この配列ではうまく言ったに過ぎないように感じました。
iがowariを超えることは在りえますでしょうか？
＊＊＊＊＊＊＊数分後↓＊＊＊＊＊＊＊＊
配列の先頭を99にして、ステップデバッグしたら、iがowariを超えて、
3個ぐらい超えたところで配列の添字オーバー（初期化されてない）適当な数字６７８２４で止まっていたことが分かりました。でも、結果i>=jなので、要素交換しないので、正しくなっていますが、
本来こういうプログラムは書かないほうが良いのではないでしょうか？
エラーの原因になりそうですし・・・。