QuickSort分区

我试图从这个网站了解快速排序算法,保罗的实施速度与stl :: sort(在大范围内快速排序,在较小范围内插入排序)。

我将保罗的实施与我的比较,我的实施慢了3倍。通过分析我们的代码,我发现主要的不确定性是分区

以下是保罗代码的摘录:

void Partition(int data[], int low , int high){
 int pivot = data[low];
 int fromLow = low;
 int fromHigh = high;
 int ptr = low;

 goto QStart;
 while(true){
    do {
        fromHigh--;
        if(fromLow >= fromHigh)
          goto QEnd;
QStart:;        
    }while(data[fromHigh] > pivot)

    data[ptr] = data[fromHigh];
    ptr = fromHigh;

    do{
        fromLow++;
        if(fromLow >= fromHigh){
          ptr = fromHigh;
          goto QEnd;
        }
    }while(data[fromLow] < pivot)
    data[ptr] = data[fromLow];
    ptr = fromLow;
 }
QEnd:;
   data[ptr] = pivot;
}

以下是我的:

void MyPartition(int data[], int low , int high){

 int pivot = data[low]; 
 int fromLow = low;
 int fromHigh = high;
 int ptr = low;
 while(fromLow != fromHigh){
    if(data[fromHigh] >= pivot)
        fromHigh--;
    else{
        data[ptr] = data[fromHigh];
        ptr = fromHigh;

        while(data[fromLow] <= pivot && fromLow != fromHigh)
            fromLow ++;
        data[ptr] = data[fromLow];
        ptr = fromLow;
    }
 }
 data[ptr] = pivot;
}

这两个函数实现了相同的算法,我相信它们具有相同的BigO:

  1. first, scanning array from high end to low end (right => left) for finding the first value is less than pivot.
  2. then, scanning array from low end to high end (left => right) for finding the first value is greater than pivot.
  3. In either scan, if anything is found, then we "swap it with pivot value", this is logical swap,because pivot value is cached with variable pivot, we can regard variable ptr as the current pivot value position.

有人知道为什么保罗的执行速度比我快吗?

UPDATE:

int PartitionData2(int * data, int low, int high){
  int pivot = data[low]; 
  int fromLow = low;
  int fromHigh = high;
  int ptr = low;

  while(fromLow < fromHigh){      
    if(data[fromHigh] > pivot)          //'>=' ==> '>'
      fromHigh--;   
    else{
      data[ptr] =data[fromHigh] ;
      ptr = fromHigh;      

      while(data[++fromLow] < pivot &&  //'<=' ==> '<'
            fromLow != fromHigh);

      data[ptr] = data[fromLow];
      ptr = fromLow;
      fromHigh--;                       //antti.huima's idea
    }
  }
  data[ptr] = pivot;
  return ptr;
}

我只是根据antti.huima的想法更新代码,这使我的代码与paul的代码一样快。

它让我感到困惑,因为它看起来像交换值等于枢轴。

UPDATE2: I understand the reason why we need move element which equals to pivot, because if we don't, the two new partitions will be uneven, e.g. there should be one is much larger than another. it eventually go to O(n^2) case.

see this PDF

3
额外 编辑
意见: 1
具有相同big-O行为的“相同”算法可以轻松地在速度上相差一个或多个数量级,具体取决于机器代码的作用,数据结构的选择等。如果您单步执行该级别汇编代码,您将看到如何加快您的速度。
额外 作者 Mike Dunlavey,
您是否实际上通过指令手动逐步完成实际的小数据集?在这两个节目中?通过参考源代码,计算指令,并记录每个指令的执行情况?
额外 作者 Mike Dunlavey,
@Chang,当你说他的算法更快时,你的意思是说它有不同的渐近行为,或者只是说给定输入花费的时间更少?
额外 作者 dsolimano,
@dsolimano,我的意思是给定输入的时间更少
额外 作者 Chang,
@MikeDunlavey,我没有看到反汇编代码有太大区别。我只是怀疑这是由分支惩罚引起的。
额外 作者 Chang,

1 答案

您的代码中有一些冗余检查,而paul的代码没有。

例如在线上

   while(data[fromLow] <= pivot && fromLow != fromHigh)

第一次检查在第一次迭代时是多余的,因为它始终认为当您开始此迭代时,在第一次迭代时,数据[fromLow]不高于pivot。原因是每当你开始这个迭代时,你刚刚从'fromHigh'交换了一个小于枢轴的值。因为对于一个随机排序的数组,这个迭代只运行几个循环(它以50%的概率终止随机数),实际上你做了25%的额外比较,而paul的代码没有进行数据透视比较在限制检查之前,但从第一次开始增加。

你在第一个循环中有相同的性能错误,你从高处减少,即使它在语法上不同。保罗的代码没有它...这就是为什么他需要转到QStart :)

2
额外
我把它更新为while(data [++ fromLow] <= pivot && fromLow!= fromHigh);它仍然很慢。你能告诉你更新的代码吗?
额外 作者 Chang,