寻找在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++快速排序/插入排序组合误差

回答

相关问题