Trying to make quick sort, program crashes

[PersonalPinky]

What is it you are trying to achieve?
I am trying to make quick sort in Turing.


What is the problem you are having?
When I run the program it compiles without errors but after a while it crashes, giving this message:
Stack overflow! Attempting to allocate 24 bytes of local variables with 28 bytes of stack space. (Original stack size: 8388608 bytes).


Describe what you have tried to solve this problem
I don't even know where to begin to fix this issue. Maybe it's the algorithm itself that is the issue, but I have made quick sort in Java with no problems.


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)

Turing:

View.Set ("graphics:max;max,nobuttonbar") const numberOfElements := 20 %number of elements in the array %Partitioning array into 2 sections: smaller than pivot and greater then pivot function partition (var a : array 1 .. * of int, left, right : int) : int     var i : int := left     var j : int := right     var temp : int     var pivot : int := a (1)     loop         exit when upper (a) = 1         if i <= j then             loop                 if a (i) < pivot then                     i += 1                 else                     exit                 end if             end loop             loop                 if a (j) > pivot then                     j -= 1                 else                     exit                 end if             end loop             if i <= j then                 temp := a (i)                 a (i) := a (j)                 a (j) := temp                 i += 1                 j -= 1             end if         else             exit         end if     end loop     result i end partition %Quick sort procedure sorts a list of integers procedure quickSort (var a : array 1 .. * of int, left, right : int)     var ind : int := partition (a, left, right)     if left < ind then         quickSort (a, left, ind)     end if     if ind < right then         quickSort (a, ind, right)     end if end quickSort %Array to be sorted var ar : array 1 .. numberOfElements of int %Initialising each element of ar to a random integer between 1-100 for i : 1 .. numberOfElements     ar (i) := Rand.Int (1, 100)     %Also outputing what the number is     put ar (i), " " .. end for %Quicksorting array quickSort (ar, 1, numberOfElements)

Please specify what version of Turing you are using
4.1.1

[wtd]

When you use recursion with a language/environment that does not support tail call optimization/elimination, stack overflows are something you will encounter.

When you call your quicksort function, the computers pushes the necessary information onto the call stack. Each time your quicksort calls itself, it does the same thing. Potentially twice.

For a large enough piece of data to sort, eventually this process will need more stack space than is available.

[Dreadnought]

A bit late but you should check the behavior of your code. Your program is getting stuck and recursing indefinitely until you run out of stack space like wtd mentioned.

[wtd]

Doesn't even have to recurse indefinitely to cause a problem.

[Dreadnought]

wtd wrote:

Doesn't even have to recurse indefinitely to cause a problem.

Agreed, I simply wanted to point out that in this case the program is getting stuck and recursing indefinitely.