quicksort algorithm throws stackoverflow exception error

Question

I have written following quick sort algorithm .But it's throwing the stack overflow exception. Any suggestion on how to fix this ..

 static void Main(string[] args)
    {
        int[] input={17,12,6,19,23,8,5,10};
        QuickSort(input,0,7);
        foreach (int item in input)
        {
            Console.WriteLine(item);
        }
    }
    static void QuickSort(int[] input,int p , int r)
    {
        if (p<r)
        {
            int q=Partition(input, p, r);
            QuickSort(input, p, q );
            QuickSort(input, q, r);
        }
    }
    static int  Partition(int [] input,int p,int r)
    {
        int pivot = input[r];//pivot element
        int i = p - 1;
        int j = r + 1;
        while (true)
        {
            do
            {
                i = i + 1;
            } while (!(input[i]>=pivot));
            do
            {
                j = j - 1;
            } while (!(input[j] <= pivot));
            //swap
            if (i<j)
            {
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
            else
            {
                return j;
            }
        }


    }

I'd suggest debugging the code, step by step, and seeing how the values of p, q and r change as you make the recursive call. Based on the error I'd guess they're not changing as they should. — carlosfigueira
– carlosfigueira, Commented Jul 16, 2013 at 16:40
A recursive QuickSort always runs the risk of blowing the stack. But not on an 8 element array. Use the debugger to trace what happens. — Henk Holterman
– Henk Holterman, Commented Jul 16, 2013 at 16:40
The recursive call QuickSort(input, p, q ); QuickSort(input, q, r); looks suspicious to me. There should be either a q-1 or a q+1. — hivert
– hivert, Commented Jul 16, 2013 at 16:46

dwonisch · Accepted Answer · 2013-07-16 18:29:44Z

1

Your QuickSort method does not stop after partitioning in case it is already sorted.

private static void QuickSort(int[] input, int p, int r) {
    if (p < r) {
        int q = Partition(input, p, r);
        if (q < r) {
            QuickSort(input, p, q);
            QuickSort(input, q, r);
        }
    }
}

answered Jul 16, 2013 at 18:29

dwonisch

5,8552 gold badges32 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Henk Holterman Over a year ago

This still looks like it could easily get stuck. And produce unsorted output.

Alexandru Lache Over a year ago

Still overflows and doesn't sort anymore

Collectives™ on Stack Overflow

quicksort algorithm throws stackoverflow exception error

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related