クイックソート3ウェイパーティション+ハイブリッド実装

Question

ハイブリッドクイックソートを使用してスリーウェイパーティションクイックソートを実装しようとしています。問題は、最後に順序付けられていないリストを取得していることです。私はHybrid QuickSortとInsertion Sortを独自にテストしており、完全に機能しています（サイズのテストは10,50,500,1000,5000）。私はデバッグを実行し、問題の内容をまだ知ることができません。前もって感謝します。ここにコードがあります。

public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) { 
    int lo = 0; 
    int hi = list.size() - 1; 

    if (hi <= lo) return; 
    int lt = lo, i = lo+1, gt = hi; 
    while (i <= gt) { 
     if (comparator.compare(list.get(i), list.get(lo)) < 0) //did not use AbstractSorter greter in order to check all cases. 
      exch(list, lt++, i++); 
     else if(comparator.compare(list.get(i), list.get(lo)) > 0) 
      exch(list, i, gt--); 
     else 
      i++; 
    } // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
    sort(comparator, list, lo, lt - 1); 
    sort(comparator, list, gt + 1, hi); 
} 

private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi){ 
    if(hi <= lo) return; 
    if(hi - lo <= 8){ 
     InsertionSort sorter = new InsertionSort(); 
     sorter.sort(comparator, list.subList(lo, hi + 1)); 
     List<SorterListener> listeners = (ArrayList)sorter.getListeners(); 
     for(SorterListener s: listeners) 
      getListeners().add(s); 
     return; 
    } 
    int i = partition(comparator, list, lo, hi); 
    sort(comparator, list, lo, i - 1); 
    sort(comparator, list, i + 1, hi); 
} 

編集：

public <T> void exch(@NotNull List<T> list, int i, int j) { 
    final T aux = list.get(i); 
    list.add(i, list.get(j)); 
    list.remove(i + 1); 
    list.add(j, aux); 
    list.remove(j + 1); 
    listeners.get(0).swap(i, j); 
} 


public <T> int partition(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) { 
    int i = lo - 1; 
    int j = hi; 
    while(true) { 
     while(greater(list, hi, ++i, comparator)) //find item left to swap 
      if (i == hi) break; 
     while(greater(list, --j, hi, comparator)) //find item right to swap 
      if (j == lo) break; 
     if (i >= j) break; //check if pointers cross 
     exch(list, i, j); //swap 
    } 
    exch(list, i, hi); //swap with partitioning item 
    return i; //return index of item now known to be in place 
} 

Answer 1

私はあなたがすることによって分割されている要素に最初sort方法（パブリック1）、ltポイントにpartitoningであなたの意図を理解していれば。この方法は、少なくとも私はそれを実行したサンプルに、正常に動作しているようです。この変更に伴い

if (comparator.compare(list.get(i), list.get(lt)) < 0) //did not use AbstractSorter greter in order to check all cases. 
     exch(list, lt++, i++); 
    else if(comparator.compare(list.get(i), list.get(lt)) > 0) 
     exch(list, i, gt--); 

：だからあなたの比較では、あなたがいないlo 1つ、ltの要素でiの要素を比較する必要がありますに。これらのアサーションを有効にすると

T v = list.get(lt); 
    for (int ix = lo; ix < lt; ix++) { 
     assert comparator.compare(list.get(ix), v) < 0 : "lt " + lt + ' ' + list; 
    } 
    for (int ix = lt; ix <= gt; ix++) { 
     assert comparator.compare(list.get(ix), v) == 0 : "lt " + lt + " gt " + gt + ' ' + list; 
    } 
    for (int ix = gt + 1; ix <= hi; ix++) { 
     assert comparator.compare(list.get(ix), v) > 0 : "gt " + gt + ' ' + list; 
    } 

、Javaがエラーをキャッチし、例えば印刷されます：

Exception in thread "main" java.lang.AssertionError: gt 2 [1, 0, 3, 6, 4, 8, 9, 5, 2, 7, 10] 

ところで、あなたのコメントは、あなたがアサーションにそれを変換することによって、より良い行うことができますNow a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].、私を助けました

この場合、gtは要素3を指しますが、リストの右側にさらに2があります。