QuickSort 的迭代实现中的无限循环？

Question

我正在尝试使用 Lomuto's Partitiong 方法实现迭代 QuickSort，因此我正在尝试实现 stack 包含一对定义要分区的子数组的索引，使用 struct 数组和两个 fields：iBeg、iEnd 和 storing/accessing 只有 end 元素。

代码如下：

function [sorted] = iterativeQuickSort(A)
% Accepts 1xN unsorted integer array.
% Returns a sorted copy.   
% See also Partition.

  % Starting and ending indexes of unsorted array.
  iBeg = 1;
  iEnd = numel(A);

  % Struct holding A's subarrays star/end indexes resulting from partitioning.
  stack_elem = struct('iBeg', iBeg, 'iEnd', iEnd); 
  stack(end + 1) = stack_elem;  % push on stack

  while numel(stack) != 0

    % Extract last pair of indexes.
    iBeg = stack(end).iBeg;
    iEnd = stack(end).iEnd;
    stack(end) = [];            % pop from stack

    % Get pivot index and array after rearranging elements around the pivot.
    [B, pivotIndex] = Partition(A, iBeg, iEnd);
    A = B;

    % Store indexes of the next two subarrays defined by the pivot index,
    % if their sizes are > 0.
    if pivotIndex - 1 > iBeg 
      stack_elem = struct('iBeg', iBeg, 'iEnd', pivotIndex - 1);
      stack(end + 1) = stack_elem;
    end  

    if pivotIndex + 1 < iEnd
      stack_elem = struct('iBeg', pivotIndex + 1, 'iEnd', iEnd);
      stack(end + 1) = stack_elem;
    end   

  end  

  sorted = A;

end  

function [A, pivotIndex] = Partition (A, iBeg, iEnd)
% Accepts 1xN integer array.  
% Two integers - start and end indexes current subarray of A.
% Returns index of pivot element of current subarray partition
% and A after swaps.

  pivotValue = A(iEnd);      % Choose last element to be pivot.
  pivotIndex = iBeg;         % Initialize pivot index to start of subarray.

  for i = iBeg : iEnd        % Iterate over current subarray
    if A(i) <= pivotValue    % Push elements <= pivot in front of pivot index.   
      % Place element at i-th position before element with pivot index.
      [A(i), A(pivotIndex)] = swapElements(A(pivotIndex), A(i)); 
      % Account for the swap, go to next element.
      pivotIndex = pivotIndex + 1;
    end  
  end  

  % Bring the element used as pivot to its place
  [A(iEnd), A(pivotIndex)] = swapElements(A(pivotIndex), A(iEnd)); 
end  

function [elem2, elem1] = swapElements(elem1, elem2)
  [elem2, elem1] = deal(elem1, elem2);  
end

明显愚蠢的数组赋值 A = B 是为了指示由于 swaps 引起的元素更改在函数 Partition(A, iBeg, iEnd).

执行后保留

目前的状态似乎是一个无限循环，其原因我无法确定，因此将不胜感激任何建议和建议！

输入：

A = [5,   4,   6,   2,   9,   1,   7,   3];
S = iterativeQuickSort(A)

预期输出：

[1, 2, 3, 4, 5, 6, 7, 9]

当前输出：从不 returns 函数，仅通过强制制动停止：ctrl + c。

注意：分区函数的实现和应用与指出可能重复的不同。

Answer 1

您的 Partition 函数有错误。如果您查看维基百科页面上的伪代码，您会看到循环条件是：

for j := lo to hi - 1 do

你的Partition函数中对应的行是：

  for i = iBeg : iEnd        % Iterate over current subarray

通过转到 iEnd 而不是 iEnd - 1，您将枢轴值与其自身进行比较，并以差一的枢轴索引结束。只需将此行更改为：

  for i = iBeg : iEnd-1      % Iterate over current subarray

QuickSort 的迭代实现中的无限循环？

Infinite loop in iterative implementation of QuickSort?

sorting

algorithm

matlab

quicksort

octave