2

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;
4

1 に答える 1

1

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-24T04:41:51.550 に答える