i am getting recursive limit crossed and not been able to get the answer when i tried to implement Median of Medians pseudo code given on Wikipedia

i am trying to implement https://en.wikipedia.org/wiki/Median_of_medians this pseudo code and i have made four fnctions same as pseudo code as following:

1.select function

function sel = select(list,left,right,n)
if (left == right)
        sel=left;
end
pivotIndex = pivot(list,left,right);
pivotIndex = partition(list,left,right,pivotIndex,n);
if (n == pivotIndex)
    sel=n;
elseif (n < pivotIndex)
    right = pivotIndex-1;
else
    left = pivotIndex+1;
end
end

2.partition function

function part = partition(list, left, right, pivotIndex, n)
     pivotValue = list(pivotIndex);
%      swap list(pivotIndex) and list(right)  // Move pivot to end
     temp = list(pivotIndex);
     list(pivotIndex) = list(right);
     list(right) = temp;
     
     storeIndex = left;
%      Move all elements smaller than the pivot to the left of the pivot
     for i=left:right-1
         if list(i) < pivotValue
%    swap list(storeIndex) and list(i)       
     temp = list(storeIndex);
     list(storeIndex) = list(i);
     list(i) = temp;
     storeIndex = storeIndex + 1;
         end
     end
     
%      Move all elements equal to the pivot right after the smaller elements
     storeIndexEq = storeIndex;
     for i=storeIndex: right-1
         if list(i) == pivotValue
%              swap list(storeIndexEq) and list(i)
     temp = list(storeIndexEq);
     list(storeIndexEq) = list(i);
     list(i) = temp;
     storeIndexEq = storeIndexEq+1;
         end
     end
     
%      swap list(right) and list(storeIndexEq)  // Move pivot to its final place
     temp = list(right);
     list(right) = list(storeIndexEq);
     list(storeIndexEq) = temp;
     
%      //Return location of pivot considering the desired location n
     if n < storeIndex
         part = storeIndex; 
     end%// n is in the group of smaller elements
     if n <= storeIndexEq
         part =  n;
     end%  // n is in the group equal to pivot
     part= storeIndexEq; %// n is in the group of larger elements 

3.pivot fnction

     function piv = pivot(list, left, right)

%      // for 5 or less elements just get median
     if (right - left) < 5
        piv = partition5(list, left, right);
       
     end
%      // otherwise move the medians of five-element subgroups to the first n/5 positions
     for i=left:5:right
%          // get the median position of the i'th five-element subgroup
         subRight = i + 4;
         if subRight > right
             subRight = right;
             
         end   
         median5 = partition5(list, i, subRight);
%          swap list[median5] and list[left + floor((i - left)/5)]
         temp = list(median5);
         list(median5) = list(left + floor((i - left)/5));
         list(left + floor((i - left)/5)) = temp;
     end

%      // compute the median of the n/5 medians-of-five
     mid = floor((right - left) / 10 + left + 1);
      piv= select(list, left, (left + floor((right - left) / 5)), mid ) ;
%        set(0,'RecursionLimit',5);
end

4. Partition5 function

function part5 = partition5( list, left, right)
     i = left + 1;
     while i <= right
         j = i;
         while (j > left) && (list(j-1) > list(j))
%              swap list[j-1] and list[j]
         temp = list(j-1);
         list(j-1) = list(j);
         list(j) = temp;
         
             j = j - 1; 
         end
         i =  i + 1;
     end
            
     part5 = floor((left + right) / 2);
     return;

i when start them in order then i get error that the recursive function has crossed limit and that has to do with the select call in pivot function. i am failed to understand it, if someone can help me to run it please. thank you

Answer 1

[Steven Lord]

In your select function:

function sel = select(list,left,right,n)
if (left == right)
        sel=left;
end
pivotIndex = pivot(list,left,right);
% snip the rest of select

if the if condition is satisfied MATLAB will assign the value of left to sel and then continue executing the rest of the select function including a call to pivot which calls select which calls pivot which calls select ...

This doesn't match the pseudocode in that Wikipedia page, which suggests that if left equals right select should return left without executing the rest of the body of the function. In MATLAB you can use the return keyword to do so. Note that you only need return if you want to return from the function before reaching the end; when MATLAB reaches the end of a function it automatically returns.

I haven't checked the rest of the pseudocode to see how many other places you'll need to do that same thing.