在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

回答

相關問題