void quicksort(int left, int right)
{
int i, j; char *x;
//if (left>=right) return;
x=words[(left+right)/2];
for(i=left,j=right;;i++,j--){
while(compare(words,x)<0){
//printf("cmp1:%scmp2:%s%d\n",words,x,compare(words,x));
i++;}
while(compare(words[j],x)>0)j--;
if(i>=j)
break;
swap(words,words[j]);
}
if(left<i-1)
quicksort(left,i-1);
if(j+1<right)
quicksort(j+1,right);
}
void swap(char x[/url],char y[/url]){
char temp[WORD_LIMIT];
int i;
for(i=0;x!=0;i++)
temp=x;
temp='\0';
for(i=0;y!=0;i++)
x=y[i];
x[i]='\0';
for(i=0;temp[i]!=0;i++)
y[i]=temp[i];
y
[i]='\0';
}
int compare(char w1[/url],char w2[/url]){
int flg=0;
int i=0;
while(w1[i]==w2[i]&&w1[i]!=0&&w2[i]!=0)
i++;
if(w1[i]>w2[i])
flg=1;
else if(w1[i]==w2[i])
flg=0;
else flg=-1;
if(flg==0){
if(w1[i]==0&&w2[i]!=0)
flg=-1;
else if(w1[i]!=0&&w2[i]==0)
flg=1;}
return flg;
}配列による文字列の辞書順クイックソート
-
R
配列による文字列の辞書順クイックソート
グローバル変数である二次元配列に格納した文字列データをクイックソートを使って辞書順にソートするプログラムを作成しています。ピボットを左端や右端にした場合は正常に動作しているようなのですが中央値((左端+右端)/2)をピボットにとると正常にソートできません。原因が分からないので指摘していただけないでしょうか。
-
non
Re:配列による文字列の辞書順クイックソート
>char *x;
>x=words[(left+right)/2];
基準値をポインタで覚えておくと、交換したときに、基準値が変わってしまいます。
char x[WORD_LIMIT];
strcpy(x,words[(left+right)/2]);
にしてください。
>x=words[(left+right)/2];
基準値をポインタで覚えておくと、交換したときに、基準値が変わってしまいます。
char x[WORD_LIMIT];
strcpy(x,words[(left+right)/2]);
にしてください。
-
R
Re:配列による文字列の辞書順クイックソート
nonさん、回答ありがとうございます。
VC++の自動変数機能でご指摘の現象を確認できましたので教えていただいた方法を試したところ正常に動いたようです。
VC++の自動変数機能でご指摘の現象を確認できましたので教えていただいた方法を試したところ正常に動いたようです。