QuickSort program reaching maximum recursion limit

Question

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:

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

I am calling this function using

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

Answer 1

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.

Two solutions:

Solution 1:

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
    % ...

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
    % ...

Answer 2

I've gone into some depth here about optimising your use of MATLAB, how you should better leverage recursive functions and a redraft of your code. To skip to the working redraft of a quicksort function, see the 2^nd and 4^th code blocks below

---

It isn't helping that in your function you're using low and high indices to keep track of your partitioning. The whole point of using a recursive quick sort function is this:

1. Pick a pivot element ar(p) from the array ar
2. Split into 2 arrays, one with values less than ar(p) and one with values greater than ar(p). Equal values can go in either array, as they will remain next to the pivot.
3. Return to step 1. with each list, repeat.

The lists are self-similar, by which I mean treat each sub-list as its own list which needs sorting, not part of a larger list! You don't need to keep track of indices (which end up confusing when you're 3 recursions deep), just analyse each list on its own.

You may find the Wikipedia article useful as it details these 3 points, as well as suggesting some schemes for optimally picking the pivot. In the below code, I just choose the middle element.

---

Additionally, your partitioning function parti is really inefficient. In MATLAB, if you find yourself looping through every index of an array then you could probably speed things up. Instead, vectorize your code using logical indexing!

At the very least, learn some more about indexing in the documentation because you can do neat things like this:

% Your code for swapping array elements
tmp = arr(i);
ar(i) = ar(r);
ar(r) = tmp;
% Using MATLAB's indexing
ar([i,r]) = ar([r,i]);

Edit: Although this demonstrates a more "MATLAB-esque" way of doing things, you incur a performance hit assigning elements like this, so if you don't mind longer code then feel free to use temps!

---

You can replace all of your code with this 7 line function, which will be much quicker. I've added comments to explain the logic...

function ar = qs(ar)
% Quicksort algorithm, for some 1D array "ar"
% First check we have more than one element, vital to terminate the recursion!
    if numel(ar) > 1
        % Choose some pivot index p, which we will split the array around
        p = ceil(numel(ar)/2);
        % Put values from "ar" which are smaller than "ar(p)" in one array
        smaller = ar(ar < ar(p));
        % Put values from "ar" which are larger than "ar(p)" in another array
        larger = ar(ar > ar(p));
        % Rebuild "ar" from a (qs-sorted) array of the smaller elemenets, then all
        % elements which were equal the pivot element (no need to sort these!) then 
        % a (qs-sorted) array of the larger elements.
        ar = [qs(smaller), ar(ar == ar(p)), qs(larger)];    
    end
end

This can be run as in your test:

ar = [7,7,3,0,3,1,4,7,5,6];
qs(ar)
>> ans = [0 1 3 3 4 5 6 7 7 7]

---

We could make this even shorter by not explicitly declaring smaller and larger, as well as always choosing p=1 (although that is the worst case for already sorted arrays).

function ar = qs(ar)
    if numel(ar) > 1
        ar = [qs(ar(ar < ar(1))), ar(ar == ar(1)), qs(ar(ar > ar(1)))];    
    end
end