Üçlü ortanca üçlüsünün genel bir fastsort'a uygulanması

Question

Bu tür bir hızlı sıralamada üçü ortanca uygulamaya çalışıyorum. Bunun hızlı bir şekilde en iyi şekilde uygulanamayacağını biliyorum ama maalesef bununla çalışmak zorunda kalıyorum.

public static <E extends Comparable<E>> void quickSort(E[] list){ 
    quickSort(list, 0, list.length - 1); 
} 

private static <E extends Comparable<E>> void quickSort(E[] list, int first, int last){ 
    if (last > first) { 
     int pivotIndex = partition(list, first, last); 
     quickSort(list, first, pivotIndex - 1); 
     quickSort(list, pivotIndex + 1, last); 
    } 
} 

private static <E extends Comparable<E>> int partition(E[] list, int first, int last){ 
    E pivot = list[first]; 
    int low = first + 1; 
    int high = last; 

    while (high > low) { 
     while (low <= high && (list[low].compareTo(pivot) <= 0)){ 
      low++; 
     } 

     while (low <= high && (list[high].compareTo(pivot) > 0)){ 
      high--; 
     } 

     if (high > low){ 
      E temp = list[high]; 
      list[high] = list[low]; 
      list[low] = temp; 
     } 
    } 

    while (high > first && (list[high].compareTo(pivot) >= 0)){ 
     high--; 
    } 

    if (pivot.compareTo(list[high]) > 0){ 
     list[first] = list[high]; 
     list[high] = pivot; 
     return high; 
    } else{ 
     return first; 
    } 
} 

Ne ilk yaptığım Jenerik diziler ile çalışacak şekilde değiştirmek olduğunu. Şimdi medyanına list dizisi dizisindeki pivotu ayarlamanız gerekiyor.

İlk üç değerin medyanını nasıl alacağımı anlıyorum. Anlamadığım şey, bu hızlı sıralama uygulamasının nasıl çalıştığını nasıl etkilediğidir.

Dönüşü medyan değere ayarladıktan sonra, bu ileri ve geri aramaları nasıl etkiler? Gösterilen kodda, low, 1 tarafından artırılan "sol" öğeye ayarlanır. Özel durumumda pivot değerini 1 artırır mıyım? Birisi, uygulamaya çalıştığım medyanın üçünün arkasındaki mantığı açıklayabilir mi?

Answer 1

Genellikle, örnek kodda görüldüğü gibi bir Lomotu tipi şema ile, [orta] ve [yüksek] değerlerle [düşük] karşılaştırın ve gerektiğinde takas yapın, böylece medyan değer dizide [düşük] biter. Bu, önceden sıralanmış veya ters sıralanmış bir diziyi sıralarken en kötü durum sorunlarını önler. İlk 3 değerin medyanının kullanılması, sipariş edilen veya iptal edilen sıralı veriler için en kötü durumları önlemez.

Hoare tipi bir bölüm şemasıyla, bu, dizinin ortasına eksen dizisini ayarlayarak ve [3] ile düşük (ve/veya) [yüksek] ile değiştirerek yapılır. dizi [pivot], orta, yüksek).