Исключение переполнения QuickSort и стека

Question

Я думаю, что QuickSort в некоторых конкретных условиях может вызвать исключение переполнения стека.

Существует два основных способа выбора элемента сворачивания во время процесса сортировки - опорным значением может быть элемент в середине отсортированного диапазона или элемент, выбранный случайным образом (в пределах отсортированного диапазона). Является ли второй метод (случайный) меньшим переполнением стека, чем первый? Не могли бы вы посоветовать мне?

Вот мой вариант быстрой сортировки (Delphi):

procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 

    procedure Sort(lLowIndex, lHighIndex: integer); 
    var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    begin 
    repeat 
     lLeft := lLowIndex; 
     lRight := lHighIndex; 
     lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle 
     //lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lLowIndex < lRight) then 
     Sort(lLowIndex, lRight); 

     lLowIndex := lLeft; 
    until lLeft >= lHighIndex; 
    end; 

begin 
    if lHighBound > lLowBound then 
    Sort(lLowBound, lHighBound); 
end; 

Спасибо за ваши советы заранее!

Mariusz.

Answer 1

Использование любого элемента с определенным индексом (первым, последним или средним), поскольку элемент поворота всегда несет риск дегенерации с конкретными наборами данных. Первый и последний элементы особенно плохи, потому что они вырождаются с предварительно заданными (или почти прерванными) данными, что довольно часто встречается. Средний элемент на практике менее проблематичен, но все еще уязвим для вредоносных построенных наборов данных.

Использование случайного элемента означает, что дегенерация может произойти только посредством чистой неудачи (если предположить, что ГСЧ не предсказуем гипотетическим нападающим), так что это хорошая тактика. Дальнейшее улучшение, которое значительно снижает вероятность попадания в эту неудачу, было бы использовать медиану из 3 (или 5 или более) случайно выбранных элементов, но она должна быть взвешена по сравнению с дополнительной сложностью и временем выполнения, которое это несет.

Answer 2

Вероятностным способом повышения эффективности является выбор трех случайных элементов и использование среднего значения (того, которое не является наибольшим или наименьшим).

Вы также можете использовать стек записей, чтобы нажимать и вызывать границы и писать цикл вместо создания рекурсивных вызовов (также он будет использовать меньше памяти, поскольку указатель на массив не будет реплицироваться для всех звонки).

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

Answer 3

Спасибо за ваши ответы.

Fortran, спасибо за ваши предложения относительно создания нерекурсивного метода. Основываясь на них, мне удалось сделать итерационный быстрый вид, и, похоже, он работает правильно :).

Вот код:

procedure QuickSortI(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 
var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    lStack: array of integer; 
    lStackLen: integer; 
begin 
    if lHighBound > lLowBound then 
    begin 
    lStackLen := 2; 
    SetLength(lStack, lStackLen); 
    lStack[lStackLen - 1] := lLowBound; 
    lStack[lStackLen - 2] := lHighBound; 

    repeat 
     lLowBound := lStack[lStackLen - 1]; 
     lHighBound := lStack[lStackLen - 2]; 
     SetLength(lStack, lStackLen - 2); 
     Dec(lStackLen, 2); 

     lLeft := lLowBound; 
     lRight := lHighBound; 
     lPivot := (lLowBound + lHighBound) div 2; 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lHighBound > lLeft) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLeft; 
     lStack[lStackLen - 2] := lHighBound; 
     end; 

     if (lLowBound < lRight) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLowBound; 
     lStack[lStackLen - 2] := lRight; 
     end; 

    until lStackLen = 0; 
    end; 
end; 

Я надеюсь, что я реализовал его оптимальным образом. Я использовал динамический массив для хранения границ сортировки (каждая пара элементов - это нижняя и верхняя границы).

Этот итерационный метод кажется немного медленнее, чем рекурсивный, но я думаю, что это не имеет большого значения.

Если вы заметили ошибку или знаете способ оптимизации метода, я буду благодарен, если вы сообщите мне об этом.

Спасибо!

Mariusz.

Answer 4

В реализации достойной реализации quicksort используется пространство стека O (log n). Это достигается тем, что сначала сортировка самого маленького подмассива. Худший случай, если вы этого не делаете, это ситуация, когда опорный элемент является самым большим элементом, и вы пытаетесь сортировать подмассиву, который каждый раз меньше одного. Это происходит, когда вы используете уже отсортированные данные в качестве ввода и принимаете в качестве поворота правый элемент.

Ваша явная реализация стека медленнее и страдает от одной и той же проблемы (хотя теперь это куча вместо стека).

Еще одна вещь, которая отсутствует, - это переход к сортировке вставки, когда подмассиво мало (5-25 элементов). Также взгляните на вопросы с двойным поворотом на этом сайте.