QuickSort程序达到最大递归限制500？ [英] QuickSort program reaching maximum recursion limit of 500?

问题描述

我正在通过在MATLAB中绘制图形来分析排序算法。以下是我的快速排序代码。当我运行它时，会出现此错误：

I am working on analysis of sorting algorithms by plotting graphs in MATLAB. Below is my quick sort code. When I run it it is giving this error:

最大递归限制为 500 到达。使用 set（0，'RecursionLimit'，N）
更改限制。请注意，超出可用堆栈空间
可能会使MATLAB和/或计算机崩溃。 ==> quickSort

Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit', N) to change the limit. Be aware that exceeding your available stack space can crash MATLAB and/or your computer. Error in ==> quickSort

为什么会发生此错误？我的代码有什么问题吗？

Why does this error occur? Is there anything wrong in my code?

function [ar] = quickSort(ar, low, high)
    if low < high
        [ar, q] = parti(ar, low, high);
        ar = quickSort(ar, low, q - 1);
        ar = quickSort(ar, q + 1, high);
    end
end

function [ar, i] = parti(ar, p, r)
    x = ar(r);
    i = p - 1;

    for j = p : r
        if ar(j) <= x
            i = i + 1;
            if i ~= j
                tmp = ar(i);
                ar(i) = ar(j);
                ar(j) = tmp;
            end
        end
    end
    i = i + 1;
    tmp = ar(i);
    ar(i) = ar(r);
    ar(r) = tmp;
end

我正在使用

ar = [7,7,3,0,3,1,4,7,5,6]
quickSort(ar, 1, 10)

推荐答案

在函数 parti ，要根据枢轴对数组进行分区，在尝试确定其正确位置时，您将包括枢轴本身。

In the function parti, to partition the array based on the pivot, you are including the pivot itself when trying to determining it's correct position.

在某些情况下，这导致无限递归，因为枢轴只是在与自己进行比较 而在相邻位置之间不断交换。

This is leading in an infinite recursion in some cases, as the pivot just keeps swapping between adjacent locations, as it is comparing with itself.

function [ar,i]= parti(ar,p,r)
    x=ar(r);
    i=p-1;

    for j=p:r-1 % Notice the r-1
        if ar(j) <= x
            i=i+1;
            if i~=j
    % ...

解决方案2：

Solution 2:

function [ar,i]= parti(ar,p,r)
    x=ar(r);
    i=p-1;

    for j=p:r
        if ar(j) < x % Notice the change in checking
            i=i+1;
            if i~=j
    % ...

这篇关于QuickSort程序达到最大递归限制500？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！