QuickSort和堆栈溢出异常 [英] QuickSort and stack overflow exception

问题描述

我认为QuickSort在某些特定条件下可能会导致堆栈溢出异常.

I think that QuickSort in some specific conditions may cause a stack overflow exception.

在排序过程中有两种选择枢轴元素的基本方法-枢轴值可以是排序范围中间的元素，也可以是随机选择的元素(在排序范围内).第二种方法(随机)是否比第一种方法少了堆栈溢出?你能告诉我吗?

There are two basic ways of selecting the pivot element during the sort process - the pivot value can be the element in the middle of the sorted range or the element chosen randomly (within the sorted range). Is the second method (random) less stack overflow prone than the first one? Could you please advise me?

这是我的快速排序(Delphi)版本:

Here is my version of quick sort (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.

推荐答案

使用任何在特定索引处(第一个，最后一个或中间)的元素作为枢轴元素总是会导致特定数据集退化的风险.第一个元素和最后一个元素特别糟糕，因为它们会随着预先排序(或几乎预先排序)的数据而退化，这是很常见的.中间元素在实践中问题较少，但仍然容易受到恶意构建的数据集的影响.

Using any element at a specific index (first, last or middle) as the pivot element always incurs the risk of degeneration with specific data sets. First and last element are particularly bad because they degenerate with presorted (or nearly presorted) data, which is quite common. The middle element is less problematic in practice, but still vulnerable to maliciously constructed datasets.

使用随机元素意味着退化只能通过纯粹的倒霉而发生(假设假设的攻击者无法预测RNG)，因此这是一个很好的策略.要显着降低遭受这种不幸影响的可能性的另一项改进是使用3个(或5个或更多)随机选择的元素的中位数，但必须权衡该方法所带来的额外复杂性和运行时间.

Using a random element means degeneration can only happen through pure bad luck (assuming that the RNG is not predictable by a hypothetical attacker), so it's a good tactic. A further improvement that significantly reduces the likelihood of being hit by that bad luck would be to use the median of 3 (or 5, or more) randomly chosen elements, but it has to be weighted against the additional complexity and running time this incurs.

这篇关于QuickSort和堆栈溢出异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！