查找 C++ 快速排序/插入排序组合中的错误

Question

我正在尝试构建一个快速排序/插入排序组合，正如一些人所说，它相当快，因为它使用快速排序处理较大的子数组，使用插入排序处理较小的数组，但有些地方肯定不正确。我一直在用我生成的一些文件测试排序。我目前正在使用一个包含 1,000,000 个数字的文件，每个数字的范围限制为 1 到 1,000,000。在添加插入排序之前，我能够在大约 0.2 秒内对 100 万个数字进行排序，在添加插入排序作为条件 if 语句之后，我很幸运在不到 4 秒的时间内对 100,000 个数字进行排序，所以我知道有一个代码中有错误，但我找不到它。我的代码只是这些类型的排序方法的不同在线参考的混合体，我不声称代码是我自己的，并且可以在必要时提供指向原始代码的链接。但是，我使用的引用不是用 C++ 编写的，而是面向 class 的，因此我不得不进行更改，这就是为什么我认为存在错误的原因。

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;
    }
}

Answer 1

如果您检查插入排序的执行，您会发现它可以对比大小 10 大得多的数组进行排序。如果您遵循由 πìντα 链接的 Lipperts writeup 中给出的优秀建议，这将被捕获ῥεῖ。

If you’ve still got a bug then first double check that your specifications contain all the preconditions and postconditions of every method.

和

If you’ve still got a bug then learn how to write assertions that verify your preconditions and postconditions.

函数调用

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

表示insertionSort对整个数组[0, last]而不是[first, last]进行操作。

更改此项，您的 modifiedQuicksort 的性能将按预期运行。

查找 C++ 快速排序/插入排序组合中的错误

Looking for error in C++ Quicksort / Insertion sort combo

c++

sorting

quicksort

insertion-sort