在Matlab中调试QuickSort

我需要帮助调试QuickSort。在我调试的时候，它实际上对阵列进行了恰当的分类，但在最后几步中，它最终会做不必要的交换，并最终返回一个未排序的数组。我花了一段时间试图弄清楚是什么造成的，但我没有取得任何进展。在Matlab中调试QuickSort

我选择了分区作为第一个元素（我知道这不是最佳的，但我只是想了解QS）。

脚本：

A = [3 6 2 5 1 7 4]; 
rightIndex = length(A); 
E = QuickSort(A,1,rightIndex);

快速排序：

function [pvt, B] = QuickSort(A,left,right) 

if left < right 
    [B, pvt] = PartnPivot1(A, left, right); %chosen pivot 
    QuickSort(B, left, pvt-1); 
    QuickSort(B, pvt+1, right); 
end

分区：

function [sortedSubArray, pivot] = PartnPivot1(subArray,leftIndex,rightIndex) 

%% Initializations 
S = subArray; 
left = leftIndex; 
right = rightIndex; 

P = S(left); %pivot 
i = left+1; 

%% Partition 
for j = i:right 
    if S(j) < P 
      temp1 = S(j); % 
      temp2 = S(i); % swap S(i) with S(j) 
      S(j) = temp2; % 
      S(i) = temp1; % 
      i = i+1; %increment i only when swap occurs 
    end 
end 
swap1 = S(left); % 
swap2 = S(i-1); % final swap 
S(left) = swap2; % 
S(i-1) = swap1; % 

sortedSubArray = S; 
pivot = P;

来源

2013-02-24 AlanH

是真的MATLAB是写快速排序的地方吗？ – 2013-02-24 01:13:06

@MitchWheat不，但我试图提高我的Matlab技能（对于Matlab我其实很新颖），所以我认为我会用Matlab来查看一些算法材料。我真的很感谢一些帮助。 – AlanH 2013-02-24 02:34:56

递归调用s到QuickSort需要将输出分配给一些变量，否则排序后的数组永远不会传回。我也认为你不需要返回数据透视表。

我打字在浏览器中，而不是在Matlab的测试，但我认为这会做...

function A = QuickSort(A,left,right) 

if left < right 
    [A, pvt] = PartnPivot1(A, left, right); %chosen pivot 
    A = QuickSort(A, left, pvt-1); 
    A = QuickSort(A, pvt+1, right); 
end

来源

2013-02-24 04:41:51 shoelzer

我得到这个错误：在调用“[...]/QuickSort.m> QuickSort”时未指定输出参数“B”（也可能是其他）。 – AlanH 2013-02-24 05:19:57

@AlanH这是因为当左> =右时B未被分配。在我的更新中，我只是使用变量A来处理所有事情。 – shoelzer 2013-02-24 16:46:41

在Matlab中调试QuickSort

回答

相关问题