Quicksort/Insertion組合比Quicksort慢嗎？

我運行Quicksort 10次，並獲得平均平均時間。我對Qicksort/Insertion排序組合做同樣的事情，它似乎比只是快速排序慢。Quicksort/Insertion組合比Quicksort慢嗎？

這裏就是我所說的插入排序

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
     int indexofpartition; 
     if(max - min > 0) { 
      if((max - min) <= 10) { 
       // Use InsertionSort now 
       InsertionSort.sort(data); 
       return; 
      } else { 
       indexofpartition = findPartition(data, min, max); 

       OptQSort2(data, min, indexofpartition - 1); 

       OptQSort2(data, indexofpartition + 1, max); 
      } 
     } 

}

和經常快速排序僅僅是同上面的代碼中的部分代碼，但沒有調用插入排序的，如果條件。

FindPartition如下：

public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) { 
    int left, right; 
    T temp, partitionelement; 
    int middle = (min + max)/2; 

    partitionelement = data[middle]; 
    left = min; 
    right = max; 

    while(left < right) { 
     while(data[left].compareTo(partitionelement) <= 0 && left < right) 
      left++; 

     while(data[right].compareTo(partitionelement) > 0) 
      right--; 

     if(left < right) { 
      temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
     } 
    }

的平均時間只是快速排序和OptSort2（使用插入排序）是

Sorted using QuickSort in: 3858841 
Sorted using OptQSort2 in: 34359610

任何想法，爲什麼？序列的大小是否重要？我爲此使用了一個1000個元素的Integer []數組。

來源

2011-12-04 sqram

「InsertionSort.sort（）」實現了遞歸還是勢在必行？ –

沒有看到QucikSort和InsertionSort的實現，這是不可能告訴的。 –

這是一個巨大的和意想不到的差距。「InsertionSort.sort」究竟做了什麼？ –

在OptQSort2，對於小的分區，你有以下函數調用：

InsertionSort.sort(data);

難道這插入排序小分區？它看起來像你插入排序整個陣列。你不應該通過min和max指數InsertionSort？

另一種選擇是在OptQSort2期間簡單地在小分區上不做任何工作。然後在OptQSort2完成其工作後，執行單個InsertionSort通過整個陣列。

來源

2011-12-04 23:15:23 Blastfurnace

您需要一個更大的整數數組才能使測試相關。此時，可能在QS + IS情況下測試if條件會減慢您的算法。

測試大量的數字，並在數據大小足夠適合L1緩存即32-64kb時切換到IS。

來源

2011-12-04 22:23:33 Tudor

一個額外的'如果'使它慢10倍？你一定是在開玩笑。 –

如果時間單位是納秒，這是可能的。:) – Tudor

該單位並不重要... –

第一個嫌疑犯顯然是你的插入排序方法。例如它是否真的排序？

您還需要對其進行10次以上的測試才能預熱JVM。而且要在兩個命令中測試它們，所以一個不會從另一個執行的升溫中受益。我會建議100或1000個測試。他們也必須都在同一個數據集上。

來源

2011-12-04 22:52:29 EJP

每次有最多10個元素的子陣列時，您都不應該致電InsertionSort。不要做任何事情：

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
    int indexofpartition; 
     if((max - min) > 10) { 
      indexofpartition = findPartition(data, min, max); 

      OptQSort2(data, min, indexofpartition - 1); 

      OptQSort2(data, indexofpartition + 1, max); 
     } 

}

當您完成調用InsertionSort爲整個陣列。

來源

2014-03-05 14:15:31 Jon

Quicksort/Insertion組合比Quicksort慢嗎？

回答

相關問題