我将执行pa与地雷相比较,地雷比执行缓慢3倍。 通过描述我们的守则,我发现主要的分裂是Partition。

The following is excerpt form paul s Code:

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

These two functions implement the same algorithm, and I believe they have the same 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.

是否有人知道,执行pa的速度快于地雷?

www.un.org/Depts/DGACM/index_spanish.htm

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

我只是根据阿蒂特·胡马的想法更新法典,这使我的法典成为 codes。

它使我感到困惑,因为它看起来像是贬低价值,等于ot。

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.