ピボットで配列を分割する

Question

ピボットの左の要素がピボットより小さく、ピボットの右の要素がピボットよりも大きいようにピボットの周りの要素を移動するための簡単なアルゴリズムを記述しようとしていますクイックソートと同じ手順）。私は動作するコードを書いていますが、その後、私はアルゴリズムを以下に変更し、動作しません。

アルゴリズムの考え方は簡単です。

2つのポインタを1つは配列の先頭に、もう1つは配列の最後にあります。 iで指し示された要素がピボットよりも小さい場合は、より大きな要素が見つかるまでスキップしてください。小さな要素より大きな要素が見つかるまでjを減少させ続ける。私は次の配列

int[] a = {46,3,8,4,2,6,244,76} 

でこれを実行すると

private static void swap(int[] a, int i , int j) 
{ 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
} 

：今すぐルーチン・コード

private static void sortByPivot(int[] a) 
{ 

    Random r = new Random(); 
    int index = r.nextInt(a.length); 
    int pivot = a[index]; 

    System.out.println("pivot = " + pivot); 

    int i =0 , j = a.length -1; 

    while(true) 
     { 

      while(a[i] <= pivot) i++; 

      while(j >0 && a[j] >= pivot) j--; 

      if(i <= j) 
      { 
       break; 
      } 
      else{ 
       swap(a,i,j); 
       } 

     } 

     swap(a,i,index); //swap the pivot and the i 
} 

スワップ

[これは一般的なアルゴリズムです]ピボットが4 として選択出力がエッジにあるいくつかの他のピボットについて

  4 3 8 46 2 6 244 76 

であり、Iは、ヌル・ポインタ例外を得ます。

実装に欠陥がありますか？論理は私のように思える。私はいつかそれを試していますが、私はそれを修正することができません。

Answer 1

これをチェックするimplementationこれはまったく同じ原理で動作します。あなたが間違っている場所を比較してみてください。

a[i]とa[j]の値をスワップする場合は、i <= jであり、ループからも外れていることに注意してください。あなたはelseでそれをやっていますが、これは間違っています。a[i]がピボットよりも大きく、ifに到達するまでにa[j]がピボットよりも小さい場合は、i <= jの場合はスワップする必要があるからです。

Answer 2

あなただけの（私はあなたが「パーティション」を言った知っているが、全部がソートされた場合、それが問題になるのでしょうか？）、それをすべてのソートしようとしている場合は、その

java.util.Arrays.sort(int[] a) 
java.util.Arrays.sort(int[] a, int fromIndex, int toIndex) 

ための方法であっ構築されています

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Arrays.html

あなたが自分で（宿題！）それを行う必要がある場合は、上記のデバッグ方法を試してください。あなたが期待するものを書いてから、何が起こるかを完全に確認してください。

Answer 3

論理が正しくありません。あなたはコードを書いたばかりです。ちょっと時間をかけて、このプログラムを任意の入力で実行してください。そして、あなたはその欠陥を直接見つけるでしょう。

ここに示したアプローチをとる方が良いでしょう。​​ これは、クイックソートで使用されているアレイを分割するインプレイスバージョンです。それがあなたの問題を解決することを願っています。