How to prevent stack overflows from quicksort algorithm using Lua?

Question

I faced a problem during my quicksort algorithm: When the input array size is bigger than 2^18 there is a good chance i get a stack overflow when executing my code:

function quickSort(array, begin_element, end_element) 
    local partitionIndex
    if (begin_element < end_element) 
    then
        partitionIndex = partition(array, begin_element, end_element);

        quickSort(array, begin_element, partitionIndex-1);
        quickSort(array, partitionIndex+1, end_element);
    end 
end

function partition(array, begin_element, end_element)
    local pivot = begin_element
    local j, tmp
    
    for j=begin_element+1, end_element, 1
    do
        if(array[j] < array[begin_element])
        then
            tmp = array[begin_element];
            array[begin_element] = array[j];
            array[j] = tmp;
        end
    end

    return pivot;
end

So i can't see where to prevent this problem with my code, since the function calls are arbitrarily recursive. So is there a possibility to manually change my stack size in VSC (or somewhere else).

I tried to google my problem, change my code so the recursions had a better execute time.

Answer 1

There are three problems at play here:

1. You're naively picking the pivot (as opposed to selecting the median, which can be found in linear time, or a random value, as the pivot); this means that in the "worst case", you get (1) quadratic time complexity and (2) linear stack depth.
2. You're doing the recursive calls in a naive order; you're not basing your order on which interval is larger, which can be used to ensure a logarithmic stack size.
3. Lua's stack size is rather limited (as opposed to languages where stacks grow until you OOM).

Possible fixes:

1. Change the LUAI_MAXSTACK compile-time constant in your luaconf.h to suit your needs and recompile Lua.
2. Use an ugly hack involving coroutines: Since each coroutine gets a fresh stack, you can simply start a coroutine to carry out recursive calls. Coroutines incur a significant memory overhead though, so only do this if you're about to hit a StackOverflow.
3. Use an algorithm with better (read: logarithmic) worst-case stack size requirements than Quick Sort, such as Merge Sort or Heap Sort.
4. Intelligently arrange your recursive calls. Intuitively, if you first sort the smaller of the two intervals, you can prove that you get at most a logarithmic stack size, as the smaller interval is as big or smaller than the "larger" ("or equal", technically) interval, thus the size of your intervals at least halves with each recursive call. You can then use a tail call to sort the larger interval, not adding to the stack depth.
5. Use a better pivot selection strategy to achieve expected O(n log n) time complexity; this can be as simple as using local pivot = math.random(begin_element, end_element). This helps with the stack overflows as well because you get expected logarithmic stack depth (no matter the order of your recursive calls); a stack overflow may remain theoretically possible, but practically won't occur as the chance for it decreases exponentially.

Abiding by your code style, implementing (4) looks as follows:

function quickSort(array, begin_element, end_element) 
    local partitionIndex
    if (begin_element < end_element) 
    then
        partitionIndex = partition(array, begin_element, end_element);

        if (partitionIndex - begin_element < end_element - partitionIndex)
        then -- partition index is closer to start => sort interval from start to index first
            quickSort(array, begin_element, partitionIndex-1);
            return quickSort(array, partitionIndex+1, end_element); -- tail call
        end
        -- partition index is closer to end => sort interval from index to end first
        quickSort(array, partitionIndex+1, end_element);
        return quickSort(array, begin_element, partitionIndex-1); -- tail call
    end 
end

And this is how your partition function may be rewritten to implement (5):

function partition(array, begin_element, end_element)
    local pivot = math.random(begin_element, end_element) -- randomly pick pivot;

    -- swap pivot to begin of interval
    array[pivot], array[begin_element] = array[begin_element], array[pivot];

    local j, tmp
    
    for j=begin_element+1, end_element, 1
    do
        if(array[j] < array[pivot])
        then
            tmp = array[pivot];
            array[begin_element] = array[j];
            array[j] = tmp;
        end
    end

    -- swap pivot back where it belows
    array[pivot], array[begin_element] = array[begin_element], array[pivot];

    return pivot;
end

---

Side note: It is unusual to see semicolons in Lua since they are (usually) optional; I'd recommend omitting them. Same for brackets around if statement conditions. You also don't have to put the then or do on the next line as if it was an opening curly brace ({); usually it's put on the same line. Furthermore, consider using local functions (which requires declaring and/or defining partition before quickSort); the step in the for loop is 1 by default already, you don't have to specify it.

Answer 2

So i found an answer for my problems:

• Pivot choosing strategy: Choose the pivot closest to the mean value of the array
• Interval processing order: Start quicksorting the smaller interval first, then go to the bigger one. This problem does not occur with big arrays, since the pivot is chosen in a way so that both intervals have nearly equal size
• Algorithm selection: I wanted to do quicksort especially, so there is no way around that.

Here is my code:

 function quickSort(array, begin_element, end_element) 
   local partitionIndex
   if (begin_element < end_element) 
   then
       partitionIndex = partition(array, begin_element, end_element);
    
       if ((end_element - (partitionIndex+1)) >= (partitionIndex-1)) then
           quickSort(array, begin_element, partitionIndex-1)
           quickSort(array, partitionIndex+1, end_element)
       else
           quickSort(array, partitionIndex+1, end_element)
           quickSort(array, begin_element, partitionIndex-1)
       end
   end 
end

function partition(array, begin_element, end_element)
   counter_calls = counter_calls + 1
   local counter = 0
   local sum = 0
   local index = begin_element - 1

   local i, k, pivot, diff, mean, pivot_val, new_pivot


   for i=begin_element, end_element
   do
       sum = sum + array[i]
       counter = counter + 1
   end
   mean = sum / counter


   diff = AbsoluteDifference(mean, array[begin_element])
   pivot = begin_element
   for k=begin_element, end_element
   do
       if (AbsoluteDifference(mean, array[k])<=diff)
       then
           diff = AbsoluteDifference(mean, array[k])
           pivot = k
       end
   end



   pivot_val = array[pivot]
   swap(array, pivot, end_element)


   for j=begin_element, end_element, 1
   do
      new_pivot = end_element
      if(array[j] <= pivot_val)
      then
         index  = index + 1
         swap(array, index, j)
         new_pivot = index
        
      end
   end

   return new_pivot;


end

By the way, i am using Windows and there was no such thing as a luaconf.h. I even tried changing the macro LUAI_MAXSTACK in C-style, but it did not work out. And when trying the coroutines, it did not sort anymore, because the threads dissolved from each other thus resulting in an incosistent array.

Anyways, thanks for your help !