Быстрая сортировка и исключение переполнения стека - PullRequest
Новая
       8

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

2 голосов
/ 03 июня 2009

Я думаю, что 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;

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

Мариуш.

Ответы [ 4 ]

4 голосов
/ 03 июня 2009

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

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

2 голосов
/ 03 июня 2009

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

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

РЕДАКТИРОВАТЬ: я заметил, что внутренняя процедура не принимает указатель в качестве параметра, поэтому забудьте, что часть ^ _ ^ в любом случае, кадр стека содержит больше информации, чем просто параметры функции, поэтому он будет по-прежнему более эффективное использование памяти (и главное, что куча, в которой выделен стек данных, обычно больше, чем стек процессов).

0 голосов
/ 21 января 2010

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

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

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

0 голосов
/ 03 июня 2009

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

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;

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

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

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

Спасибо!

Мариуш.

...