杜克對同一數據

的不同shufflings ninther在實施改進快速排序的分區，我試圖用杜克的ninther找到支點（借入QuickX.java幾乎一切從塞奇威克的實現）杜克對同一數據

我的代碼下面給出了不同的結果，每次整數數組被混洗。

import java.util.Random; 
public class TukeysNintherDemo{  
    public static int tukeysNinther(Comparable[] a,int lo,int hi){ 
     int N = hi - lo + 1; 
     int mid = lo + N/2; 
     int delta = N/8; 
     int m1 = median3a(a,lo,lo+delta,lo+2*delta); 
     int m2 = median3a(a,mid-delta,mid,mid+delta); 
     int m3 = median3a(a,hi-2*delta,hi-delta,hi); 
     int tn = median3a(a,m1,m2,m3); 
     return tn; 
    } 

    // return the index of the median element among a[i], a[j], and a[k] 
    private static int median3a(Comparable[] a, int i, int j, int k) { 
     return (less(a[i], a[j]) ? 
       (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) : 
       (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i)); 
    } 

    private static boolean less(Comparable x,Comparable y){ 
     return x.compareTo(y) < 0; 
    } 
    public static void shuffle(Object[] a) { 
    Random random = new Random(System.currentTimeMillis()); 
     int N = a.length; 
     for (int i = 0; i < N; i++) { 
      int r = i + random.nextInt(N-i);  // between i and N-1 
      Object temp = a[i]; 
      a[i] = a[r]; 
      a[r] = temp; 
     } 
    } 
    public static void show(Comparable[] a){  
     int N = a.length; 
     if(N > 20){ 
      System.out.format("a[0]= %d\n", a[0]); 
      System.out.format("a[%d]= %d\n",N-1, a[N-1]); 
     }else{ 
      for(int i=0;i<N;i++){ 
       System.out.print(a[i]+","); 
      } 
     } 
     System.out.println(); 

    } 
    public static void main(String[] args) { 
     Integer[] a = new Integer[]{17,15,14,13,19,12,11,16,18}; 
     System.out.print("data= "); 
     show(a); 
     int tn = tukeysNinther(a,0,a.length-1); 
     System.out.println("ninther="+a[tn]); 
    } 
} 

Running this a cuople of times gives 

data= 11,14,12,16,18,19,17,15,13, 
ninther=15 

data= 14,13,17,16,18,19,11,15,12, 
ninther=14 

data= 16,17,12,19,18,13,14,11,15, 
ninther=16

對於同一個數據集的不同數據混合，tuckey's ninther會給出不同的值嗎？當我試圖手工找到中位數的中位數時，我發現代碼中的上述計算是正確的。這意味着與數據集的中位數不同，相同的數據集產生不同的結果。這是否是正確的行爲？有更多統計知識的人可以評論嗎？

來源

2013-07-13 damon

排序後的數組是一個排序後的數組。如果你洗牌數據，然後排序它，你應該總是以相同的數據。中位數是中間值;在相同的數據中，它也應該始終是相同的。就像中庸或模式一樣。也許看看[這]（http://stackoverflow.com/questions/12545795/explanation-of-the-median-of-medians-algorithm）和[this]（http://stackoverflow.com/questions/9489061/瞭解-中位數的中位數算法）。 –

另一個說明;我想這是某種運動或測試？由於Java在['Arrays']（http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html）和['Collections']（http：// docs.oracle.com/javase/7/docs/api/java/util/Collections.html）來完成您在此編碼的許多事情。 'Arrays.toString'，'Collections.shuffle'，當然還有'Arrays.sort'。 –

我想學習一些算法的東西..不試圖解決任何問題，使用Java庫.. – damon

杜克的ninther檢查9項，並計算使用僅的中位數。

對於不同的隨機洗牌，您可能會得到不同的Tukey's ninther，因爲可能會檢查不同的項目。畢竟，您總是會檢查相同的陣列插槽，但不同的隨機播放可能會在這些插槽中放入不同的項目。

這裏的關鍵是Tukey's ninther是而不是給定數組的中位數。這是一個嘗試性的中位數應用，只需很少的努力：我們只需要讀取9個項目並進行12個比較就可以得到它。這比獲得實際中位數要快得多，並且與「三位數中位數」相比，導致不希望的中位數的可能性較小。請注意，機會依然存在。

這個回答你的問題？

在附註中，有人知道使用Tukey's ninther的快速排序是否仍然需要洗牌？我假設是，但我不確定。

來源

2013-10-04 12:23:03 Timo

我剛剛意識到使用Tukey的ninther的確定性（即*非*混合）快速排序當然容易受到惡意輸入的影響。所以洗牌確實是必需的。 – Timo

杜克對同一數據

回答

相關問題