0

I have this Quick Sort Implementation using the left as its pivot and when passing an array of 10240 random numbers it gives an exception. When passing an array of 1024 random numbers it sorts my array normally without giving an exception.

System.StackOverflowException was unhandled HResult=-2147023895
Message=Exception of type 'System.StackOverflowException' was thrown. InnerException:

 public int[] SortQuick(int[] arr, int left, int right)
    {
         if (left < right)
        {
            int pivot = Partition(arr, left, right);
            if (pivot > 1)
                SortQuick(arr, left, pivot - 1);
            if (pivot + 1 < right)
                SortQuick(arr, pivot + 1, right);
        }
        return arr;
    }


    public int Partition(int[] numbers, int left, int right)
    {
        int pivot = numbers[left];
       while (true)
        {
            while (numbers[left] < pivot)
                left++;
            {
                while (numbers[right] > pivot)
                    right--;
                if (left < right)
                {
                    int temp = numbers[right];
                    numbers[right] = numbers[left];
                    numbers[left] = temp;
                }
                else
                {
                    return right;
                }
            }
        }
    }

Main Program

int[] num2 = aGen.AlmostOrdered(10240, 0);
QuickSort q = new QuickSort();
q.SortQuick(num2,0,num2.Length-1);

aGen is a class which generates random numbers.

3
  • There's obviously a problem with your recursion then. What does the stack look like when it overflows - what's the pattern of left and right values? Commented May 23, 2016 at 13:13
  • 1
    Your QuickSort is the common recursive version then yes, you may get StackOverflowException. However you can rewrite it to be non-recursive.. Commented May 23, 2016 at 13:14
  • I'd guess picking the left-hand element as the pivot always is inefficient, if your input is partially sorted too: you want to try and split the range equally. Commented May 23, 2016 at 13:31

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.