Оптимизация или неправильная реализация QuickSort

Question

Delphi имеет эту реализацию QuickSort в одном из образцов:

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer); 
var 
    Lo, Hi, Mid, T: Integer; 
begin 
    Lo := iLo; 
    Hi := iHi; 
    Mid := A[(Lo + Hi) div 2]; 
    repeat 
    while A[Lo] < Mid do Inc(Lo); 
    while A[Hi] > Mid do Dec(Hi); 
    if Lo <= Hi then 
    begin 
     VisualSwap(A[Lo], A[Hi], Lo, Hi); // just for visual 
     T := A[Lo]; 
     A[Lo] := A[Hi]; 
     A[Hi] := T; 
     Inc(Lo); 
     Dec(Hi); 
    end; 
    until Lo > Hi; 
    if Hi > iLo then QuickSort(A, iLo, Hi); 
    if Lo < iHi then QuickSort(A, Lo, iHi); 
    if Terminated then Exit; 
end; 

Он работает, но разделение кажется странным. Или это общая оптимизация?

Я сделал тест со случайными значениями, и вы получите случаи, когда Mid не находится в Hi, Lo или между ними. И в этом случае «шарнир» попадает между двумя значениями. Это связано с тем, что он увеличивает и Lo, и Hi после флип, даже когда одно из них имеет значение Mid. Не подсказка, которую вы держите за значение Pivot, и делайте еще один QuickSort с левой и с правой стороны. Это оптимизация для равных ключевых значений?

Кроме того, эта реализация имеет равную ценность? Будет ли 3-стороннее разделение лучше?

Answer 1

одна ошибка в коде:

середине = (низкая + высокая) DIV 2 может переполниться при использовании массива вблизи максимального Integer.

решить с помощью: средний = низкий ДИВ 2 + высокая ДИВ 2

подробное обсуждение см Algorithms

после чтения, которые связывают вы должны знать, что:

Является ли это оптимизация равные значения ключа?

Нет, проблема с равными значениями отсутствует. (quicksort не является стабильным видом)

Кроме того, имеет ли эта реализация вопрос равной ценности? Будет ли 3-стороннее разделение лучше?

Нет проблем. Нет, почему это должно быть лучше? Оптимизация может быть выполнена с использованием выбора случайного элемента поворота.

Answer 2

Прошу прокомментировать меня, поскольку я не уверен, что это лучший способ сделать это.

Я пытаюсь понять суть QuickSort. Я думаю, что эта поправка будет сделать эту работу реализация лучше (игнорировать VisualSwap, это только для демо визуальных эффектов):

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer); 
var 
    Lo, Hi, Mid, T: Integer; 
begin 
    Lo := iLo; 
    Hi := iHi; 
    T := (Lo + Hi) div 2; 
    VisualSwap(A[Lo], A[T], Lo, T); 
    Mid := A[T]; 
    A[T] := A[Lo]; 
    A[Lo] := Mid; 

    inc(Lo); 
    //Mid := A[(Lo + Hi) div 2]; 
    repeat 
    while A[Lo] < Mid do Inc(Lo); 
    while A[Hi] > Mid do Dec(Hi); 
    if Lo <= Hi then 
    begin 
     VisualSwap(A[Lo], A[Hi], Lo, Hi); 
     T := A[Lo]; 
     A[Lo] := A[Hi]; 
     A[Hi] := T; 
     Inc(Lo); 
     Dec(Hi); 
    end; 
    until Lo > Hi; 

    if Hi > iLo then 
    begin 
    VisualSwap(A[iLo],A[Hi],iLo,Hi); 
    A[iLo] := A[Hi]; 
    A[Hi] := Mid; 
    dec(Hi); 
    end; 

    if Hi > iLo then QuickSort(A, iLo, Hi); 
    if Lo < iHi then QuickSort(A, Lo, iHi); 
    if Terminated then Exit; 
end; 

То, что я сделал, было съехать ключ, находя стержень, затем вставил ключ в ось и только быстрая сортировка вне этой ключевой точки.

Answer 3

Я также тестировал разные варианты со средой 3 и т. Д. Единственное, что давало некоторое ускорение, было создание гибрида между сортировкой quicksort и insertion и разворачиванием одной из рекурсий. Я удалил ключевую часть, поскольку ничего не дал. Вот окончательный вариант моего тестирования:

procedure QuickSort3(var A: array of integer; iLo, iHi: integer); 
var 
    Hi, Lo, T, Mid: integer; 
begin 
    repeat 
    if (iHi-iLo) > 16 then 
    begin 
     Mid := A[(iHi + iLo) shr 1]; 
     Lo := iLo; 
     Hi := iHi; 
     repeat 
     while A[Lo] < Mid do inc(Lo); 
     while A[Hi] > Mid do dec(Hi); 
     if Lo <= Hi then 
     begin 
      if Lo <> Hi then 
      begin 
      T := A[Lo]; 
      A[Lo] := A[Hi]; 
      A[Hi] := T; 
      end; 
      inc(Lo); 
      dec(Hi); 
     end; 
     until Hi < Lo; 
     if Hi > iLo then 
     QuickSort3(A,iLo,Hi); 
     iLo := Lo; 
    end 
    else 
    begin 
     for Lo := iLo + 1 to iHi do 
     begin 
     T := Arr[Lo]; 
     Hi := Lo; 
     while (Hi > iLo) and (Arr[Hi-1] > T) do 
     begin 
      Arr[Hi] := Arr[Hi-1]; 
      dec(Hi); 
     end; 
     Arr[Hi] := T; 
     end; 
     exit; 
    end; 
    until iHi <= Lo; 
end; 

Усиление было около 1,4 секунды на 100 миллионов случайных значений.

Во всяком случае, что я узнал до сих пор:

разбиение на разделы правильно, вам не нужно обрабатывать ключ. Многие учебники QuickSort объясняют это «неправильным». Неправильно в том смысле, что это не нужно.

Было мало выгоды при работе с ключом. Вы получаете немного меньше звонков, но вы также получаете штраф за дополнительную обработку, и они примерно одинаковы. В целом, я получил 50-100 мс быстрее при обработке ключей при сортировке 100 миллионов значений (всего 13,9 секунды). Но это на компиляторе Delphi.

вставки рода дали достаточно хорошо, чтобы иметь внутри сортировки, когда элементы находятся ниже 16.