quicksortについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
primary
記事: 2
登録日時: 7年前
住所: jp

quicksortについて

#1

投稿記事 by primary » 7年前

quicksortのどこが間違っているのかよくわかりません。
単語を辞書順(逆)に出力したいんですが、一部の単語は入れ替えを行われていないようです。何回も繰り返すと正しい結果が出ます。
誰か教えていただけませんか。よろしくお願いします。

コード:

void quick_sort(char a[][WORD_LENGTH_MAX], int left, int right) {

  char temp_char[1][WORD_LENGTH_MAX];

  int l = left;
  int r = right;
  int s;

  s = (left + right) / 2;

  while(1){
    while(stricmp(a[l], a[s]) > 0) l++;
    while(stricmp(a[s], a[r]) > 0) r--;
    if(l >= r) break;

    strcpy(temp_char[0], a[l]);
    strcpy(a[l], a[r]);
    strcpy(a[r], temp_char[0]);

    l++;
    r--;

  }

  if(left < l - 1)
    quick_sort(a, left, l - 1);
  if(right > r + 1)
    quick_sort(a, r + 1, right);

}

アバター
みけCAT
記事: 6351
登録日時: 10年前
住所: 千葉県
連絡を取る:

Re: quicksortについて

#2

投稿記事 by みけCAT » 7年前

入れ替えの過程でaが書き換えられる可能性があるのがまずいかもしれません。
ピボットを別のバッファに退避させてみてください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

初級者
記事: 200
登録日時: 10年前

Re: quicksortについて

#3

投稿記事 by 初級者 » 7年前

それはそれとして、私からみると、
[1] と定義している配列は
本当に必要なのか?
という気がします。

non
記事: 1097
登録日時: 10年前

Re: quicksortについて

#4

投稿記事 by non » 7年前

特に、間違っているところはないように見えますが、DEBUGしてみないとわかりません。
具体的に、mainやデータを入れた、再現性のあるプログラムを載せてもらえますか?
non

primary
記事: 2
登録日時: 7年前
住所: jp

Re: quicksortについて

#5

投稿記事 by primary » 7年前

みけCAT さんが書きました:入れ替えの過程でaが書き換えられる可能性があるのがまずいかもしれません。
ピボットを別のバッファに退避させてみてください。


ご回答ありがとうございます。解決できました。

ほかの皆さんにも感謝します。

閉鎖

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