配列による文字列の辞書順クイックソート

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
R

配列による文字列の辞書順クイックソート

#1

投稿記事 by R » 16年前

グローバル変数である二次元配列に格納した文字列データをクイックソートを使って辞書順にソートするプログラムを作成しています。ピボットを左端や右端にした場合は正常に動作しているようなのですが中央値((左端+右端)/2)をピボットにとると正常にソートできません。原因が分からないので指摘していただけないでしょうか。
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;
}

non

Re:配列による文字列の辞書順クイックソート

#2

投稿記事 by non » 16年前

>char *x;
>x=words[(left+right)/2];

基準値をポインタで覚えておくと、交換したときに、基準値が変わってしまいます。
char x[WORD_LIMIT];
strcpy(x,words[(left+right)/2]);
にしてください。

R

Re:配列による文字列の辞書順クイックソート

#3

投稿記事 by R » 16年前

nonさん、回答ありがとうございます。
VC++の自動変数機能でご指摘の現象を確認できましたので教えていただいた方法を試したところ正常に動いたようです。

閉鎖

“C言語何でも質問掲示板” へ戻る