标签: quicksort

我正在尝试使用linq使用C#实现一个功能样式的快速排序,这个代码随机工作/不起作用,我无法弄清楚为什么.
重要的是:当我在数组或列表上调用它时,它工作正常.但是在一个未知的 - 它真的是IEnumerable,它变得疯狂(失去价值或崩溃,通常.有时工作.)
代码:

   public static IEnumerable<T> Quicksort<T>(this IEnumerable<T> source)
        where T : IComparable<T>
    {
        if (!source.Any())
            yield break;
        var pivot = source.First();
        var sortedQuery = source.Skip(1).Where(a => a.CompareTo(source.First()) <= 0).Quicksort()
                          .Concat(new[] { pivot })
                          .Concat(source.Skip(1).Where(a => a.CompareTo(source.First()) > 0).Quicksort());
        foreach (T key in sortedQuery)
            yield return key;
    }

Run Code Online (Sandbox Code Playgroud)

你能在这里发现任何可能导致失败的故障吗？

编辑:一些更好的测试代码:

        var rand = new Random();
        var ienum = Enumerable.Range(1, 100).Select(a => rand.Next());
        var array = ienum.ToArray();
        try
        {
            array.Quicksort().Count();
            Console.WriteLine("Array went fine.");
        }
        catch (Exception ex)
        { …

Run Code Online (Sandbox Code Playgroud)

为什么在排序列表而不是快速排序时,mergesort被认为是"走的路"？我在网上看过的一个讲座中听到了这个,并在几个网站上看到过.

在C++中使用openMP时我再次陷入困境.这次我正在尝试实现并行快速排序.

码:

#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <omp.h>
#include <stdio.h>

#define SWITCH_LIMIT 1000

using namespace std;

template <typename T>
void insertionSort(std::vector<T> &v, int q, int r)
{
    int key, i;
    for(int j = q + 1; j <= r; ++j)
    {
        key = v[j];
        i = j - 1;
        while( i >= q && v[i] > key )
        {
            v[i+1] = v[i];
            --i;
        }
        v[i+1] = key;
    }
}

stack<pair<int,int> > s;

template <typename T>
void …

我有一个看似非常基本的问题,但它是在"每个CPU滴答计数"的背景下(这是将在超级计算机上使用的更大算法的一部分).

问题很简单:对无符号长long int数及其原始索引列表进行排序的最快方法是什么？(开头时,unsigned long long int数字是完全随机的.)

Example :
Before
Numbers: 32 91 11 72
Indexes: 0 1 2 3
After
Numbers: 11 32 72 91
Indexes: 2 0 3 1 

通过"最快的方式",我的意思是:使用什么算法:std :: sort,C qsort,或网上提供的其他排序算法？使用什么容器(C数组,std :: vector,std :: map ...)？如何同时对索引进行排序(使用结构,std :: pair,std :: map ...)？

非常感谢你 !

编辑:要排序多少元素？ - >通常4Go数字

我正在阅读一些文本声称有关两个递归Quicksort调用的顺序:

...首先调用较小的子问题很重要,这与尾递归一起确保堆栈深度为log n.

我完全不确定这意味着什么,为什么我应该首先在较小的子阵列上调用Quicksort？

我正在阅读Robert Sedwick算法和数据结构第1-4部分中的快速排序算法.

template <class item>

static void quicksort(item [] a, int l, int r)
{
    if(r <= l) return;
    int i = partition(a,l,r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

template <class item>
int partition(item a[], int l, int r)
{
    int i = l-1; j = r; item v = a[r];

    for(;;) {
        while( a[++i] < v );
        while( v < a[--j] ) 
            if( j == l ) 
                break;
        if( i >= j) 
            break;  // pointer crossing.
        exch(a[i], a[j]); …

我在C#中实现了一个quicksort版本,并执行了一些快速基准来与C#进行比较List<T>.Sort.我发现我的实现比库版本慢得多.我想知道为什么.这是一些粗略的基准数字.对于输入,我使用了一个随机(均匀)生成的整数列表,其中包含很少的重复元素.请注意,所有基准时间均为多次运行的平均值.

100,000 elements
My code         0.096 seconds
List<T>.Sort    0.011 seconds

1,000,000 elements
My code         1.10 seconds
List<T>.Sort    0.14 seconds

我的代码如下.以下是我尝试过的优化列表及其结果:

• 在线 - 我试图在线Swap和 我的ChoosePivotIndex功能内嵌,我看到了大约10%的改进.
• 枢轴选择 - 我知道我正在使用天真的枢轴选择方法.我也试过使用三个随机元素的中位数.这并没有带来太大的改善.我猜这是因为我用于基准测试的输入数据是均匀随机的.
• 并行性 - 我尝试并行进行递归分区调用.这似乎实际上增加了执行时间.
• 特殊外壳小输入 - 我已经尝试切换到小输入的插入排序(如List<T>.Sort声称做).这产生了大约20%的改善.

通过这些优化的组合,我已经能够将我的代码降低到

100,000 elements -   0.062 seconds
1,000,000 elements - 0.740 seconds 

这仍然比库Sort慢得多.在我的代码中有没有明显的解释性能差距,或者是从更小的调整中剩下的70-80%的差距？请注意,下面的代码是我未经优化的基础版本

public class Quicksorter<T> where T : IComparable<T>
{
    protected Random random;
    public Quicksorter()
    {
        random = new Random();
    }

    public void Sort(IList<T> …

我已经在一些地方看到以下代码建议添加到数字并除以2,特别是在查找数组中间索引以进行快速排序的上下文中.

int middle = ( low + high ) >>> 1;

反对 int middle = ( low + high ) / 2;

如果我在基础知识上错了,请纠正我.右移位1位(>> 1)具有除以2的效果.因为在java int中,我们不想改变第一位,所以我们使用无符号移位运算符>>>.我听说这可以防止整数溢出,但我不知道如何.根据docs算术运算符主导轮班.这是一个有争议的问题,因为无论如何都要使用括号.如果( )溢出中的任何东西为什么外面的东西很重要？

我很难理解quicksort,大多数演示和解释都忽略了实际发生的事情(例如http://me.dt.in.th/page/Quicksort/).

维基百科说:

从数组中选择一个称为pivot的元素.分区:对数组进行重新排序,使得值小于枢轴的所有元素都在枢轴之前,而所有值大于枢轴的元素都在它之后(相等的值可以是任意一种).在此分区之后,枢轴处于其最终位置.这称为分区操作.递归地将上述步骤应用于具有较小值的元素的子数组,并分别应用于具有较大值的元素的子数组.

如何使用9,1,7,8,8的数组,例如以7为枢轴？9需要移动到枢轴的右侧,所有快速排序实现都是现场操作,所以我们不能在8,8之后添加它,所以唯一的选择是将9与7交换.

现在阵列是7,1,9,8,8.quicksort背后的想法是,现在我们必须递归地将部件分类到枢轴的左侧和右侧.枢轴现在位于数组的位置0,这意味着没有左侧部分,因此我们只能对正确的部分进行排序.这是没有用的7> 1所以枢轴最终在错误的地方.

在这个图像4是枢轴,那么为什么5几乎一直向左？它大于4!经过大量的交换后,它最终被排序,但我不明白这是怎么回事.

我正在阅读M.Mitzenmacher和E.Upfal的" 概率与计算 ".我在理解如何计算两个元素的比较概率时遇到问题.

输入:数字的排序列表(y1,y2,...,yN).我们正在寻找枢轴元素(随机).问题:两个元素yi和yj(j> i)的概率是多少？

答案(来自书): yi和yj将被比较,如果yi或yj将被选为第一次从序列中绘制的枢轴(yi,yi + 1,...,yj-1,yj).所以可能性是:2 /(j-i + 1).

对我来说问题是最初的主张:例如,在整个列表的第一次抽奖中拾取yi将导致与yj的比较(反之亦然),概率为2/n.

因此,相反"反向"声明是正确的 - 在yi或yj之前不能选择(yi + 1,...,yj-1)元素,但"池"大小不固定(在第一次绘制中)它肯定是N,但在第二个它更小).

有人可以解释作者如何提出这样一个简化的结论吗？

Edit1:一些好心灵打磨了我的帖子,谢谢:-).

Edit2:列表最初排序.