クイックソートのプログラムについて

質問

一から自分なりにやってみましたが、再帰処理の部分がうまくゆきません。
改善方法をご教授願えたらと思います。

#include<stdio.h>

void
qsort (int x[], int a, int b)
{
　int temp, kijyun, i;
　kijyun = a;
　i = a + 1;

　while (i <= b)
　　{
　　　if (x[i] < x[kijyun])
　　　　{
　　　　　change (x, kijyun, i);
　　　　　kijyun = kijyun + 1;
　　　　}
　　　i++;
　　}

　if (kijyun != 0) //基準より左側をソートする。
　　{
　　　qsort (x, 0, kijyun - 1);
　　}

//以下if文の部分で、うまくいきません。
　if (kijyun != 9) //基準より右側をソートする。
　　{
　　　qsort (x, kijyun + 1, 9);
　　}
}

int
change (int x[], int a, int b) //x[b]をx[a]の位置に挿入させる。
{
　int i, temp;
　i = b;

　while (i != a)
　　{
　　　temp = x[i];
　　　x[i] = x[i - 1];
　　　x[i - 1] = temp;
　　　i--;
　　}
}

int
main (void)
{
　int i, x[9] = { 6, 8, 9, 5, 3, 2, 1, 4, 7 };
　qsort (x, 0, 8);
　for (i = 0; i != 9; i++)
　　{
　　　printf ("\n%d", x[i]);
　　}
}

回答No.2

buriburi3

>配列をx[0]からx[8]まで用意しているこのプログラムでは、bは8に固定されているはずだと思うのですが、8を入れてみるとなぜか動きません、どうしてなんでしょうか・・・

この質問はQSORTの原理を全く理解していないから出る質問ですが…
初回の検索範囲は0-8ですが2回目以降の検索範囲は0-閾値までと閾値-8までに分割されます。

お礼

確かにそうですね。
処理対象範囲を狭めていくなかで、その狭められた要素の閾値の左半分と”右半分”も処理しなければいけませんね。
回答ありがとうございます。少し、勘違いしていました。

qsort内の左右を処理させるif文は、それぞれ、”初めに分けられた後”の左側のすべて、また、右側すべてを処理すると思い込んでいました。

（このプログラムの配列に与えている値では、初めに6を閾値とした後の、左半分は、その左半分のみを処理する動作だけで、きれいに並び替えられてしまいます。また、右半分も同様になります。実際、片方のif文を消して、動作させると、6から左側、或いは右側が、きれいに並んでしまいます。）

考えてみると、もうひとつのif文も0固定ではおかしいですね。
　if (kijyun != a) //基準より左側をソートする。
　　{
　　　qsort (x, a, kijyun - 1);
　　}
のように、0をaとすべきでした。

回答No.1

asuncion

>qsort (int x[], int a, int b)

このように、ソートする範囲を引数で与えて、
汎用的であるはずの関数で、

>　if (kijyun != 9) //基準より右側をソートする。
>　　{
>　　　qsort (x, kijyun + 1, 9);

ここが9で固定になっているのはどうしてでしょうか。

お礼

返信ありがとうございます。
確かに、ごもっともな意見ですね。本来は、
　if (kijyun != b) //基準より右側をソートする。
　　{
　　　qsort (x, kijyun + 1, b);
　　}
のように、9をbにすべきですね。
これで実行してみると、ちゃんと動きました。
どうも、ありがとうございます。なんというか、初歩的なミスですいません・・・

私は、プログラミング完成前までは、考えやすいように具体的な数値を入れておくことがあるのですが、そうだとしても、配列はx[0]からx[8]までなので、bは9ではなく8でした。

ただ、配列をx[0]からx[8]まで用意しているこのプログラムでは、bは8に固定されているはずだと思うのですが、8を入れてみるとなぜか動きません、どうしてなんでしょうか・・・