QuickSort Partition

Question

Я пытаюсь понять алгоритм быстрой сортировки с этого веб-сайта , реализация Павла так же быстро, как 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. сначала, сканирование массива от верхнего до нижнего конца (справа => слева) для Нахождение первого значения меньше, чем пивот.
2. затем, сканирование массива от нижнего до верхнего конца (влево => вправо) для найти первое значение больше, чем пивот.
3. В любом сканировании, если что-то найдено, мы "меняем его местами" со сводным значением ", это логический своп, потому что сводное значение кэшируемый с переменной pivot , мы можем рассматривать переменную ptr как текущее значение разворота положение.

Кто-то знает, почему реализация Павла быстрее, чем у меня?

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, это делает мои коды такими же быстрыми, как и коды Павла.

Это сбивает меня с толку, потому что это выглядит как обменное значение, равное pivot.

UPDATE2 : Я понимаю причину, по которой нам нужен элемент перемещения, равный pivot, потому что, если мы этого не сделаем, два новых раздела будут неравномерными, например, должно быть одно намного больше другого. это в конечном итоге перейти к O (n ^ 2) случае.

см. этот PDF

Answer 1

В вашем коде есть несколько лишних проверок, которых нет у кода Павла.

Например, на линии

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

первая проверка избыточна на первой итерации, поскольку она всегда гласит, что при запуске этой итерации данные на первой итерации [fromLow] не выше, чем сводная точка. Причина в том, что всякий раз, когда вы запускаете эту итерацию, вы просто меняете значение меньше, чем пивот от fromHigh. Поскольку для произвольно упорядоченного массива эта итерация выполняется только для пары циклов (она заканчивается с вероятностью 50% для случайного пивота), на практике вы делаете на 25% больше сравнений по сравнению с кодом Пола, который не выполняет сравнение с пивом перед проверкой предела, но увеличивается с первого раза на нижний.

У вас та же ошибка производительности в первом цикле, когда вы уменьшаете значение с High, хотя оно синтаксически отличается. у кода Павла его нет ... и поэтому ему нужно перейти к QStart:)