CODEWITHSUNDEEP
c#algorithm
krrishna
krrishna

Reputation: 2078

quicksort algorithm throws stackoverflow exception error

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;
            }
        }


    }

Upvotes: 1

Views: 677

Answers (1)

dwonisch
dwonisch

Reputation: 5785

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);
        }
    }
}

Upvotes: 1

Related Questions