尋找在C++快速排序/插入排序組合誤差

-5

我試着去建立一個快速排序/插入排序組合，如某些人所說的相當快的，因爲它剷球與快速排序較大的子陣列，並插入排序較小陣列中的事，但肯定是不正確的。我一直在測試我生成的一些文件的排序。我目前使用的是1,000,000個數字的文件，每個數字的範圍限制是從1到1,000,000。在此之前將插入排序，我能1萬個號碼在0.2秒左右，增加插入排序爲條件if語句，我很幸運100,000號碼少於4秒排序後進行排序，所以我知道有一個代碼錯誤，但我找不到它。我的代碼只是這些類型的排序方法的不同在線參考的混合物，我沒有聲稱代碼是我自己的，並且可以根據需要提供原始鏈接。然而，我使用的引用不是用C++編寫的，並且是面向類的，所以我必須進行更改，這就是我認爲存在錯誤的原因。尋找在C++快速排序/插入排序組合誤差

void modifiedQuickSort(arrPtr &arrayPointer, int first, int last) 
{ 
    int firstTemp = first, lastTemp = last; 
    int temp; 
    int pivot = arrayPointer[(first + last)/2]; 


    if((last - first) < 10) 
    { 
     insertionSort(arrayPointer, last + 1); 
    } 

    else 
    { 
     // Partitioning Step 
     while (firstTemp <= lastTemp) 
     { 
      while (arrayPointer[firstTemp] < pivot) 
       firstTemp++; 

      while (arrayPointer[lastTemp] > pivot) 
       lastTemp--; 

      if (firstTemp <= lastTemp) 
      { 
       temp = arrayPointer[firstTemp]; 
       arrayPointer[firstTemp] = arrayPointer[lastTemp]; 
       arrayPointer[lastTemp] = temp; 
       firstTemp++; 
       lastTemp--; 
      } 
     } 

     // Recursive step 
     if (first < lastTemp) 
      modifiedQuickSort(arrayPointer, first, lastTemp); 

     if (firstTemp < last) 
      modifiedQuickSort(arrayPointer, firstTemp, last); 
    } 
} 

void insertionSort(arrPtr &arrayPointer, const int &arraySize) 
{ 
    int i, key, j; 

    for (i = 1; i < arraySize; i++) 
    { 
     key = arrayPointer[i]; 

     j = i-1; 

     /* Move elements of arr[0..i-1], that are 
     greater than key, to one position ahead 
     of their current position */ 
     while (j >= 0 && arrayPointer[j] > key) 
     { 
      arrayPointer[j+1] = arrayPointer[j]; 
      j = j-1; 
     } 
     arrayPointer[j+1] = key; 
    } 
}

來源

2016-11-13 joe_04_04

使用正確的工具來解決這些問題是你的調試器。在*堆棧溢出問題之前，您應該逐行執行您的代碼。如需更多幫助，請閱讀[如何調試小程序（由Eric Lippert撰寫）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，您應該\編輯您的問題，以包含一個[最小，完整和可驗證]（http://stackoverflow.com/help/mcve）示例，該示例再現了您的問題，以及您在調試器。 –

我對調試器非常熟悉，這是我一直在使用的。問題是，算法的工作原理。排序沒有問題（到目前爲止）。但是，調試器無法告訴我爲什麼該算法不如其預期的那樣高效，或者甚至遠不如單獨Quicksort一樣高效。我會嘗試編輯它以幫助其他人運行。 –

你插入排序可能是有效的多用在already-排序段二進制搜索來尋找插入點。線性搜索最終會加起來。 – WhozCraig

如果檢查插入的執行那種你看到它得到排序遠遠更大的陣列比大小10這將被抓，你就跟着Lipperts writeup通過πάνταῥεῖ鏈接提供的優秀建議。

如果你仍然有一個bug，那麼首先要檢查你的規範是否包含所有方法的所有前置條件和後置條件。

和

如果你仍然有一個bug然後學習如何編寫驗證您的前置或後置斷言。

函數調用

if((last - first) < 10) 
{ 
    insertionSort(arrayPointer, last + 1); 
}

表示insertionSort整個陣列[0, last]不[first, last]上操作。

改變這一點，你modifiedQuicksort的業績預期行爲。

來源

2016-11-13 09:51:48

這解決了它。謝謝。 –

尋找在C++快速排序/插入排序組合誤差

回答

相關問題