クイックソートで無限ループしてしまう。

Question

クイックソートのアルゴリズムを自分で書こうとしたのですが、上手くいきません。具体的に言うと、配列の数字がすべて違っていれば問題ないのですが、基準値となる値が重複している場合、無限ループになってしまうのです。

public class Quick {

	public static void main(String[] args) {
		int[] array = {4,8,6,1,2,9,0,3,5,7};
		int datum = array[0];//先頭の値を基準値とする
		
		System.out.println("配列arrayの中身は");
		System.out.println(java.util.Arrays.toString(array) + "です。");
		System.out.println("クイックソートで一回だけソートします。");
		System.out.println();
		
		for(int left = 0,right = array.length-1;left < right;){
			/*配列の左側から走査。
			 *基準値、または基準値以上の値を見つけるまで続ける。
			 */
			while(array[left] < datum){
				left++;
			}
			/*配列の右側から走査。
			 *基準値、または基準値以下の値を見つけるまで続ける。
			 */
			while(array[right] > datum){
				right--;
			}
			//left,rightが入れ替わっていなかったら値を交換する。
			if(left < right){
				int tmp = array[left];
				array[left] = array[right];
				array[right] = tmp;
			}
		}
		
		System.out.println("配列arrayは");
		System.out.println(java.util.Arrays.toString(array));
		System.out.println("になりました。");

	}

}

//実行結果
配列arrayの中身は
[4, 8, 6, 1, 2, 9, 0, 3, 5, 7]です。
クイックソートで一回だけソートします。

配列arrayは
[3, 0, 2, 1, 4, 9, 6, 8, 5, 7]
になりました。
//基準値より左側は基準値以下の値、右側は基準値以上の値になる。

この配列だとうまくいくのですが、例えば
int[] array = {4,8,6,1,2,9,0,3,5,4}
だった場合、最初と最後の４の交換を無限に行ってしまうのです。

if(array[left] == array[right]) で処理しようと思ったのですが、どういう風に処理すればいいのかわかりませんでした。どこを直したらいいのでしょうか。

Answer 1

/*配列の左側から走査。
 *基準値、または基準値以上の値を見つけるまで続ける。
 */
while(array[left] < datum){
    left++;
}

か

/*配列の右側から走査。
 *基準値、または基準値以下の値を見つけるまで続ける。
 */
while(array[right] > datum){
    right--;
}

のどっちかが<=か>=じゃないとうまく動かない

Comments

[退会済みユーザー]

これはすでに試していて、確かにこうすれば無限ループは回避できるんですが、正しくクイックソートできないんですよ。
[4, 4, 3, 1, 2, 0, 9, 6, 5, 8]
か
[3, 0, 2, 1, 6, 9, 8, 4, 5, 4]
になる…ってあれ？　よく見ると下の配列は１と６の間で基準値以下と基準値以上に分かれていますね。ちょっと勘違いしていました。ありがとうございます。

[退会済みユーザー]

勘違いしていた部分がわかった。分割点は基準値があるところじゃなくて、ソートが終わった後のleftの位置なのか。