当数组具有重复值时,为什么快速排序算法的持续时间会增加?

哈立德

我正在尝试使用std :: chrono时间计算并使用在[A,B]范围内的随机生成的整数数组来测量Merge Sort和Quick Sort函数的持续时间,该数组的大小从5000到100,000个整数不等。

我的代码的目的是证明,当改进快速排序中拾取(pivot)的方法时,快速排序功能最终花费的时间比合并排序所花费的时间更少,因此我选择枢轴的方式是使用随机索引方法可最大程度地降低复杂度为(n ^ 2)的可能性,但是在某些情况下(我将在下面进行描述),快速排序最终比合并排序要花费更多的时间,我想知道为什么会这样。

情况1:数组中数字的范围很小,这增加了在数组中重复数字的可能性。

情况2:当我使用像clion这样的本地IDE时,快速排序功能比合并排序花费更多的时间,但是,像IDEONE.com这样的在线编译器在两种排序算法中给出的结果相似(即使所生成整数的范围为小)

这是我在上述情况下得到的结果(第一行数字是合并排序结果,第二行是快速排序结果):

1-clion可缩小数字范围(-100、600) clion结果数字范围狭窄(-100、600)

2-clion结果的数字范围很广(INT_MIN,INT_MAX) clion结果的数字范围很广(INT_MIN,INT_MAX)

3-IDEONE结果的数字范围较小(-100、600) IDEONE结果的数字范围较小(-100、600)

4- IDEONE结果的范围很广(INT_MIN,INT_MAX) IDEONE的结果范围很广(INT_MIN,INT_MAX)

#include <bits/stdc++.h>
#include <chrono>
#include <random>

using namespace std;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int* generateArray(int size)
{
    int* arr = new int[size];
    uniform_int_distribution<> distribution(INT_MIN, INT_MAX);
    for (int i=0; i < size; ++i)
    {
        arr[i] = distribution(gen);
    }
    return arr;
}
void merge(int* leftArr, int nL, int* rightArr, int nR, int* mainArr)
{
    int i=0, j=0, k=0;
    while (i < nL && j < nR)
    {
        if (leftArr[i] < rightArr[j]) { mainArr[k++] = leftArr[i++]; }
        else { mainArr[k++] = rightArr[j++]; }
    }
    while (i < nL){ mainArr[k++] = leftArr[i++]; }
    while (j < nR){ mainArr[k++] = rightArr[j++]; }
}
void mergeSort (int* mainArray, int arrayLength)
{
    if (arrayLength < 2) { return; }
    int mid = arrayLength/2;
    int* leftArray = new int[mid];
    int* rightArray = new int[arrayLength - mid];
    for (int i=0; i<mid; ++i) {leftArray[i] = mainArray[i];}
    for (int i = mid; i<arrayLength; ++i) {rightArray[i - mid] = mainArray[i];}
    mergeSort(leftArray, mid);
    mergeSort(rightArray, arrayLength-mid);
    merge(leftArray, mid, rightArray, arrayLength-mid, mainArray);
    delete[] leftArray;
    delete[] rightArray;
}


int partition (int* arr, int left, int right)
{
    uniform_int_distribution<> distribution(left, right);
    int idx = distribution(gen);
    swap(arr[right], arr[idx]);
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; ++i)
    {
        if (arr[i] <= pivot)
        {
            swap(arr[i], arr[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(arr[right], arr[partitionIndex]);
    return partitionIndex;
}
void quickSort (int* arr, int left, int right)
{
    if(left < right)
    {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
}

int main()
{
    vector <long long> mergeDuration;
    vector <long long> quickDuration;
    for (int i = 5000; i<= 100000; i += 5000)
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        quickSort(arr, 0, i - 1);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        quickDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 5000; i <= 100000; i += 5000 )
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        mergeSort(arr, i);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        mergeDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 0; i<mergeDuration.size(); ++i)
    {
        cout << mergeDuration[i] << " ";
    }
    cout  << endl;
    for (int i = 0; i<quickDuration.size(); ++i)
    {
        cout << quickDuration[i] << " ";
    }
}
生锈的

当输入集包含大量重复项时,Quicksort表现出较差的性能。解决方案是使用维基百科上所述的三向分区

重复元素

With a partitioning algorithm such as the ones described above (even with one that chooses good pivot values), quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly apparent when all the input elements are equal: at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the algorithm takes quadratic time to sort an array of equal values.

To solve this problem (sometimes called the Dutch national flag problem), an alternative linear-time partition routine can be used that separates the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. ... The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. In pseudocode, the quicksort algorithm becomes

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

The partition algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition. Every item of the partition is equal to p and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls to quicksort.

进行以下修改可以quickSort得到更好的结果:

pair<int,int> partition(int* arr, int left, int right)
{
    int idx = left + (right - left) / 2;
    int pivot = arr[idx]; // to be improved to median-of-three
    int i = left, j = left, b = right - 1;
    while (j <= b) {
        auto x = arr[j];
        if (x < pivot) {
            swap(arr[i], arr[j]);
            i++;
            j++;
        } else if (x > pivot) {
            swap(arr[j], arr[b]);
            b--;
        } else {
            j++;
        }
    }
    return { i, j };
}
void quickSort(int* arr, int left, int right)
{
    if (left < right)
    {
        pair<int, int> part = partition(arr, left, right);
        quickSort(arr, left, part.first);
        quickSort(arr, part.second, right);
    }
}

输出:

0 1 2 3 4 5 6 7 8 9 11 11 12 13 14 15 16 19 18 19
0 0 0 1 0 1 1 1 1 1 2 3 2 2 2 2 3 3 3 3

0 1 2 3 4 5 6 6 8 8 9 12 11 12 13 14 16 17 18 19
0 0 1 1 1 2 3 3 3 4 4 4 5 6 5 6 7 7 8 8

因此,现在有很多重复的运行要快得多。

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

为什么当我为CABasicAnimation设置较低的持续时间值时,它会跳吗?

来自分类Dev

计算Prometheus指标具有特定值的持续时间?

来自分类Dev

为什么CSS动画没有持续时间?

来自分类Dev

具有持续时间的定期事件

来自分类Dev

增加dismissViewControllerAnimated()的持续时间

来自分类Dev

D3.js在具有不同持续时间的每个元素上重复过渡

来自分类Dev

根据日期+持续时间(分钟)对数组(甘特图时间表)进行排序-带有静态间隔(日期+持续时间)

来自分类Dev

为什么在瞬间日期中添加以秒为单位的持续时间,对于1个月以上的值会产生怪异的结果?

来自分类Java

为什么未成年GC持续时间的变化这么大,当大数组的元素被更新?

来自分类Dev

UIView-具有持续时间的动画似乎忽略了持续时间

来自分类Dev

Debug.DrawLine:为什么持续时间过后,行没有消失?

来自分类Dev

为什么在Glimpse SQL选项卡上有2个持续时间?

来自分类Dev

Spark UI输出操作持续时间与作业持续时间:有什么区别?

来自分类Dev

为什么GCC / Clang接受const限定对象作为具有静态存储持续时间的对象的初始化程序?

来自分类Dev

有什么办法可以在持续时间的svg动画标签中赋予多个值?

来自分类Dev

为什么记录持续时间而不查询?

来自分类Dev

为什么Application_ResolveRequestCache的持续时间很长?

来自分类Dev

JavaScript 加载具有特定持续时间的图像

来自分类Dev

消除具有静态存储持续时间的变量

来自分类Dev

合并具有不同持续时间的视频和音频

来自分类Dev

FFMPEG:复用具有不同持续时间的流

来自分类Dev

FFMPEG图像序列具有不同的持续时间

来自分类Dev

具有动态元素的CSS动画持续时间

来自分类Dev

在JavaScript中更改具有不同持续时间的文本

来自分类Dev

如何获得具有多行的天数的持续时间总和?

来自分类Dev

如何运行具有特定持续时间的函数?

来自分类Dev

PHP的:增加持续时间

来自分类Dev

PHP 增加会话持续时间

来自分类Dev

增加视频FFMPEG C ++的持续时间

Related 相关文章

  1. 1

    为什么当我为CABasicAnimation设置较低的持续时间值时,它会跳吗?

  2. 2

    计算Prometheus指标具有特定值的持续时间?

  3. 3

    为什么CSS动画没有持续时间?

  4. 4

    具有持续时间的定期事件

  5. 5

    增加dismissViewControllerAnimated()的持续时间

  6. 6

    D3.js在具有不同持续时间的每个元素上重复过渡

  7. 7

    根据日期+持续时间(分钟)对数组(甘特图时间表)进行排序-带有静态间隔(日期+持续时间)

  8. 8

    为什么在瞬间日期中添加以秒为单位的持续时间,对于1个月以上的值会产生怪异的结果?

  9. 9

    为什么未成年GC持续时间的变化这么大,当大数组的元素被更新?

  10. 10

    UIView-具有持续时间的动画似乎忽略了持续时间

  11. 11

    Debug.DrawLine:为什么持续时间过后,行没有消失?

  12. 12

    为什么在Glimpse SQL选项卡上有2个持续时间?

  13. 13

    Spark UI输出操作持续时间与作业持续时间:有什么区别?

  14. 14

    为什么GCC / Clang接受const限定对象作为具有静态存储持续时间的对象的初始化程序?

  15. 15

    有什么办法可以在持续时间的svg动画标签中赋予多个值?

  16. 16

    为什么记录持续时间而不查询?

  17. 17

    为什么Application_ResolveRequestCache的持续时间很长?

  18. 18

    JavaScript 加载具有特定持续时间的图像

  19. 19

    消除具有静态存储持续时间的变量

  20. 20

    合并具有不同持续时间的视频和音频

  21. 21

    FFMPEG:复用具有不同持续时间的流

  22. 22

    FFMPEG图像序列具有不同的持续时间

  23. 23

    具有动态元素的CSS动画持续时间

  24. 24

    在JavaScript中更改具有不同持续时间的文本

  25. 25

    如何获得具有多行的天数的持续时间总和?

  26. 26

    如何运行具有特定持续时间的函数?

  27. 27

    PHP的:增加持续时间

  28. 28

    PHP 增加会话持续时间

  29. 29

    增加视频FFMPEG C ++的持续时间

热门标签

归档