クイックソートのアルゴリズムを自分で書こうとしたのですが、上手くいきません。具体的に言うと、配列の数字がすべて違っていれば問題ないのですが、基準値となる値が重複している場合、無限ループになってしまうのです。
java
1public class Quick { 2 3 public static void main(String[] args) { 4 int[] array = {4,8,6,1,2,9,0,3,5,7}; 5 int datum = array[0];//先頭の値を基準値とする 6 7 System.out.println("配列arrayの中身は"); 8 System.out.println(java.util.Arrays.toString(array) + "です。"); 9 System.out.println("クイックソートで一回だけソートします。"); 10 System.out.println(); 11 12 for(int left = 0,right = array.length-1;left < right;){ 13 /*配列の左側から走査。 14 *基準値、または基準値以上の値を見つけるまで続ける。 15 */ 16 while(array[left] < datum){ 17 left++; 18 } 19 /*配列の右側から走査。 20 *基準値、または基準値以下の値を見つけるまで続ける。 21 */ 22 while(array[right] > datum){ 23 right--; 24 } 25 //left,rightが入れ替わっていなかったら値を交換する。 26 if(left < right){ 27 int tmp = array[left]; 28 array[left] = array[right]; 29 array[right] = tmp; 30 } 31 } 32 33 System.out.println("配列arrayは"); 34 System.out.println(java.util.Arrays.toString(array)); 35 System.out.println("になりました。"); 36 37 } 38 39} 40
//実行結果 配列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}
だった場合、最初と最後の4の交換を無限に行ってしまうのです。
if(array[left] == array[right]) で処理しようと思ったのですが、どういう風に処理すればいいのかわかりませんでした。どこを直したらいいのでしょうか。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/01/04 09:59
退会済みユーザー
2016/01/04 12:08