Исключение быстрой сортировки и переполнения стека

Question

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

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

Вот моя версия быстрой сортировки (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

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

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

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

Answer 3

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

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

Вот код:

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

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

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

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