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

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