クイックソート3ウェイ分割

Question

私は要素がピボットと等しいゾーンを区切るためのインデックスとして "m1"と "m2"を使用して、3ウェイパーティションテクニックでクイックソートアルゴリズムを実装しようとしています。 は、ここに私のコードです：

public class Sorting { 
private static Random random = new Random(); 

private static int[] partition3(long[] a, int l, int r) { 
    long x = a[l]; 
    int m1 = l; 
    int m2 = l; 

    for (int i = l + 1; i <= r; i++) { 
     if (a[i] < x) { 
      m1++; 
      m2++; 
      swap(a, m1, m2); 

     } 

     if (a[i] == x) { 
      m2++; 
      swap(a, i, m1); 
     } 
    } 
    swap(a, l, m1); 


    int[] m = {m1, m2}; 
    return m; 
} 

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

private static void randomizedQuickSort(long[] a, int l, int r) { 
    if (l >= r) { 
     return; 
    } 
    int k = random.nextInt(r - l + 1) + l; 
    long t = a[l]; 
    a[l] = a[k]; 
    a[k] = t; 
    int m[] = partition3(a, l, r); 
    randomizedQuickSort(a, l, m[0] - 1); 
    randomizedQuickSort(a, m[1] + 1, r); 
} 

public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    long[] a = new long[n]; 
    for (int i = 0; i < n; i++) { 
     a[i] = scanner.nextLong(); 
    } 
    randomizedQuickSort(a, 0, n - 1); 
    for (int i = 0; i < n; i++) { 
     System.out.print(a[i] + " "); 
    } 
} 

} 

倍の大半を、それは私のテストに正しい答えを出力し、時にはません。誰かが私が間違っていることを教えてもらえますか？

Answer 1

あなたのコードは、リスト内で繰り返し番号がある場合に失敗します。例えば、あなたのコードは、テストケース失敗：

をそれは別の何かに乱数生成のためにすべての時間を返しますが、それは正解ではありません。これは、partition3()関数の問題です。具体的には、forループの中で、どこをインクリメントして反転させるかを決める場合です。この場合、

if (a[i] < x) { 
    m1++; 
    m2++; 
    swap(a, m1, m2); 
} 

i番目のインデックスを適切な場所に移動するスワップがありません。そのスワップは次のようになります。

if (a[i] < x) { 
    m1++; 
    m2++; 
    swap(a, m1, m2); 
    swap(a, m1, i); //The missing swap. 
} 

他のif条件では、2つの欠落があります。まず、両方のif条件の意図しない入力を避けるために、else-ifにする必要があります。第二に、間違った場所でスワップします。 m1ではなく、m2（2番目の壁）にスワップする必要があります。これは、第2の壁が最初のものではなくピボットと同じ値を扱うからです。修正され、2番目のifの条件はそれほどのようになります。これらの修正で

else if (a[i] == x) { //Note the addition of the else 
    m2++; 
    swap(a, i, m2); //Corrected, now swaps at m2 
} 

は、あなたのコードが意図したとおりに動作するようです。

Answer 2

「m1」と「m2」（「等しい」ゾーンの2つの区切り文字）が反対側から始まると、はるかに簡単です。要素がピボットよりも小さい場合は、左の区切り記号と入れ替え、ピボットより大きい場合は、右の区切りにスワップします。それ以外の場合は、等しい場合は、単に "i"インデックスを移動します。

private static int[] partition3(long[] a, int l, int r) { 
    long x = a[l]; 
    int m1 = l; 
    int m2 = r; 

    int i = l + 1; 

    while(i <= m2) { 
     if (a[i] > x) { 
      swap(a, i, m2); 
      m2--; 
     } else if (a[i] < x) { 
      swap(a, m1, i); 
       m1++; 
      i++; 
     } else { 
      i++; 
     } 
    } 

    int[] m = {m1, m2}; 
    return m; 
}