QuickSort的迭代实现无限循环

Question

我正在尝试使用lomuto的partitiong方法来实现迭代 QuickSort ，因此我试图实现 stack 使用两个struct的数组，其中有两个 fields： iBeg， iEnd，并仅存储/仅访问 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是指在执行函数Partition(A, iBeg, iEnd)后保留swaps引起的元素更改。

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

输入：

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

预期输出：

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

电流输出：永远不要从功能返回，仅通过力制动：ctrl c停止。

注意：分区函数的实现和应用与指向重复的指向。

---

Answer 1

您的Partition功能有错误。如果您查看Wikipedia页面上的伪代码，您会发现循环条件是：

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