プログラマ専用SNS ミクプラ

クイックソートの分割アルゴリズムには誤りがあるそうなのですが、どこがおかしいのかわかりません。

コード:

int i = low;
int j = high;
	
while (i <= j) {
	while (a[i] <= x) i++;
	while (a[j] => x) j--;
	if(i <= j) {
		//a[i] とa[j] を入れ替える;
		i++; j--;
	}
}

どのような誤りがおきるのでしょうか？

xの定義がわかりませんが、xがaの要素の一つと等しいとすると、aの中身が全て同じ時に範囲外アクセスで死にます。
コード(クイックソートの関数？)全体を貼っていただけるとわかりやすくなります。

また、実装を誤る可能性はありますが、
一般に知られている「クイックソートの分割アルゴリズム」自体に間違いがある可能性は低いと考えられます。

返信ありがとうございます。
xの定義について書くのを忘れていました。
xはlowからhighまでの区間を分割する基準値としています。
x=a[low];
です。

実はこれは大学のテストの過去問なのでプログラム全体のソースコードはないんです。
答えがないので、質問させていただきました。
問題文をすべてのせます。

問題
クイックソートにおける分割アルゴリズムを次のように実装した。
このアルゴリズムは、配列aの添え字lowから添え字high間での区間をa[low]を基準値として分割することを目的としているが誤りを含んでいる。

コード:

int i = low;
int j = high;
int x = a[low];
	
while (i <= j) {
	while (a[i] <= x) i++;
	while (a[j] => x) j--;
	if(i <= j) {
		//a[i] とa[j] を入れ替える;
		i++; j--;
	}
}

(1)low = 0, high = 5で実行したときに、この分割アルゴリズムが正しく動作するような入力例（a[0],....a[5]の6要素の列）をひとつ挙げ、アルゴリズム実行後の配列aの内容とiとjの値を示せ。ただし、入力例とする値の列は、
{5,9,4,2,8,6}の６個の整数値を適切に並べ替えたものとする。

(2)low = 0, high = 5で実行したときに、この分割アルゴリズムが正しく動作しないような入力例（a[0],....a[5]の6要素の列）をひとつ挙げ、その例に対してアルゴリズムを実行したときにどのような誤りが起きるかを述べよ。ただし、入力例とする値の列は、
{5,9,4,2,8,6}の６個の整数値を適切に並べ替えたものとする。

以上が問題文です。
(1)に関しては考えてみたのですが、最初から整列済みの入力例であれば正しく動作するのではないかと思いました。つまり、
{2,4,5,6,8,9}が答えであっていますか？

(2)はよくわかりません。

よろしくお願いします。

HISA さんが書きました:(1)に関しては考えてみたのですが、最初から整列済みの入力例であれば正しく動作するのではないかと思いました。つまり、
{2,4,5,6,8,9}が答えであっていますか？

iとjの値を示していないので、あっていないと思います。

HISA さんが書きました:(2)はよくわかりません。

常にa<=xであるような配列aを与えればいいです。
すなわち、x==a[0]がaのなかで最大の値ならばいいです。
もしくは、常にa[j]=>xである(a[0]がaの中で最小)ような配列aを与えてもいいですね。
どのような誤りがおきるかはシュミレーション(脳内/実際に実行)してみてください。

よく考えたら、標準のJavaに"=>"という演算子はないようなのですが、これは何でしょうか？

プログラマ専用SNS ミクプラ

Java クイックソート

Java クイックソート

Re: Java クイックソート

Re: Java クイックソート

Re: Java クイックソート

Re: Java クイックソート