-2

MatLab でクイック ソートを実装しようとしています。2 つの関数があります。1 つは指定されたリストを 2 つの小さなリストに分割し、1 つはピボットよりも大きく、もう 1 つは小さいリストに分割します。2 番目の関数は、クイック ソートを再帰的に呼び出し、次に小さいリストを反復処理して、クイック ソートを再度呼び出します。私のコードは以下です。ランダムに生成された 300 個の数値のリストを使用してコードを実行すると、「メモリ不足です。プログラム内の無限再帰が原因である可能性があります。」というエラーが表示されます。

function [ less, pivot, greater ] = SplitList( list, pivotindex )
%List Splitting Function
%In order to preform quick sort you firts must be able to split the list 
%into two, one which is greater than, and one which is less than the pivot.

pivot = list(1,pivotindex);

greater = [];
less = [];

for l = 1:length(list)
    if list(1,l) > pivot
        greater = [greater list(1, l)];
    else if list(1,l) <= pivot
        less = [less list(1, l)];
        end
    end

end

end

function [ qs_list ] = quick_sort( list )
%Recursive Quick Sort
%   quick sort algorithm to sort a list of numbers

%set (0,'RecursionLimit',1000);
pivotindex = round(length(list)/2); %sets pivot at the median value of the array

if length(list) > 1
    [ less, pivot, greater ] = SplitList( list, pivotindex ); %calls the SplitList function
    qs_list = [quick_sort(less) pivot quick_sort(greater)]; %calls quick_sort within the function

else
    qs_list = list;

end
end
4

1 に答える 1

1

リストは、再帰呼び出しごとに 1 つの要素を増やします。

を見てみましょう。返されSplitList()たless要素の数と返された要素の数を足したものgreaterが、引数の要素の数ですlist。

ただし、 で並べ替えられたリストを再帰的に組み立てると、 、 、およびquick_sort()が連結され、 に比べてサイズが 1増加します。lessgreater pivotqs_listlist

組み立て手順は次のようになります。

    qs_list = [quick_sort(less) quick_sort(greater)];

後で編集

クイック ソートの長所の 1 つは、その場でソートできることです(つまり、ソートされていないリストとソートされたリストに同じメモリ領域を使用します)。これにより、ソートが必要な要素の重複が回避されます。

つまりlist、引数として取得したものと同じ変数を返す必要があります。そうしないと、呼び出しごとに 2 倍のメモリが消費されます。並べ替えられていないlistリストの N 要素と、部分的に並べ替えられたリストlessとgreater. 平均時間の計算量を O(N×log(N)) とすると、O(2 N×log(N) ) = O(N×2 N ) のメモリを消費します。300 要素のメモリが不足するのも不思議ではありません。

次のように書き換えてみてくださいSplitList。

function list = SplitList(list, beginindex, endindex, pivotindex)
    ...

また、quick_sort同じように書き直す必要があります。

于 2016-10-05T20:27:41.397 に答える