How can I prevent my Quicksort Algorithm from throwing a StackOverflowException

Question

Im trying to write a quicksort algorithm in C#, and I've been getting System.StackOverflowExceptions for the last while and can't figure out why.

Here is my Class:

    class quicksort : sortalgorithm
{
    int pivotIndex = -1;
    int pivotSwapped = 0;
    Random rand = new Random();

    public quicksort(int[] arr)
    {
        if (arr.Length < 5)
        {
            throw new Exception("Array has too few Entries");
        }
        toSort = arr;
    }

    protected override int sort()
    {
        if (pivotIndex == -1) getPivot();
        int indexL = getIndexLeft();
        int indexR = getIndexRight();
        if (indexR != -1 && indexL != -1 && indexL != toSort.Length-1)
        {
            swap(indexL, indexR);
        }
        if (indexL > indexR)
        {
            Console.WriteLine("Index thingy");
            swap(toSort.Length - 1, indexL);
            pivotSwapped++;
            if (pivotSwapped == toSort.Length - 1)
            {
                return 1;
            }
            else
            {
                Console.WriteLine("new piv");
                pivotSwapped++;
                getPivot();
                sort();
                return -1;
            }
        }
        else
        {
            sort();
            return -1;
        }
    }

    private void swap(int i, int j)
    {
        int temp = toSort[i];
        toSort[i] = toSort[j];
        toSort[j] = temp;
    }

    private void getPivot()
    {
        pivotIndex = rand.Next(0, toSort.Length - 1);
        swap(toSort.Length - 1, pivotIndex);
    }

    private int getIndexLeft() // Larger then Pivot Starting: Left
    { //Error Here
        int itemFromLeft = -1;
        for (int i = 0; i < toSort.Length - 1; i++)
        {
            if (toSort[i] >= toSort[toSort.Length - 1])
            {
                itemFromLeft = i;
                i = toSort.Length + 1;
            }
        }
        //Console.WriteLine(itemFromLeft);
        return itemFromLeft;
    }

    private int getIndexRight()// Smaller then Pivot Starting: Right
    {
        int itemFromRight = -1;
        for (int i = toSort.Length - 1; i >= 0; i--)
        {
            if (toSort[i] < toSort[toSort.Length - 1])
            {
                itemFromRight = i;
                i = -1;
            }
        }
        //Console.WriteLine(itemFromRight);
        return itemFromRight;
    }
}

I hope that someone can help me.

P.S. the class sortalgorithm in this case only has the the array toSort.

My Console output always looks a bit like this:

[4, 28, 62, 33, 11] // The unsorted array
Index thingy
new piv
Index thingy
new piv
Index thingy
new piv

Process is terminated due to `StackOverflowException`.

Answer 1

This simple implementation of Hoare partition scheme demonstrates how to avoid stack overflow by recursing on the smaller partition, and looping back for the larger partition, an idea used in the original quicksort. Stack space complexity is limited to O(log2(n)), but worst case time complexity is still O(n^2).

        static public void Quicksort(int [] a, int lo, int hi)
        {
            while(lo < hi){                 // while partition size > 1
                int p = a[(lo + hi) / 2];
                int i = lo, j = hi;
                i--;                        // Hoare partition
                j++;
                while (true)
                {
                    while (a[++i] < p) ;
                    while (a[--j] > p) ;
                    if (i >= j)
                        break;
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
                i = j++;                    // i = last left, j = first right
                if((i - lo) <= (hi - j)){   // if size(left) <= size(right)
                    Quicksort(a, lo, i);    //   recurse on smaller partition
                    lo = j;                 //   and loop on larger partition
                } else { 
                    Quicksort(a, j, hi);    //   recurse on smaller partition
                    hi = i;                 //   and loop on larger partition
                }
            }
        }

Answer 2

a stack overflow error usually happens when you have a error in your recursion , ie a function keeps calling itself until there is no room left in the stack to hold all the references,

the only obvious candidate is

            **sort();**
            return -1;
        }
    }
    else
    {
        **sort();**
        return -1;
    }

so either one or the other recursive calls is probably incorrect and needs removing and i suspect the issue will be resolved

EDIT:

as you are unable to debug your code this is what a quick sort should look like

public int sort()
{
    qsort(0, toSort.Length - 1);
    return 0;
}

private void qsort( int left, int right)
{
    if (left < right)
    {
        int pivot = Partition( left, right);

        if (pivot > 1)
        {
            qsort( left, pivot - 1);
        }
        if (pivot + 1 < right)
        {
             qsort( pivot + 1, right);
        }
    }
}
private int Partition( int left, int right)
{
    int pivot = toSort[left];
    while (true)
    {

        while (toSort[left] < pivot)
        {
            left++;
        }

        while (toSort[right] > pivot)
        {
            right--;
        }

        if (left < right)
        {
            if (toSort[left] == toSort[right]) return right;

            int temp = toSort[left];
            toSort[left] = toSort[right];
            toSort[right] = temp;


        }
        else
        {
            return right;
        }
    }
}

Note that if left >= right do nothing