Quick Sort working for small input - Need Fresh Pair of eye to find bug

35 views Asked by At

I know there are lot of resources on QuickSort but I need a fresh pair of eyes to catch a bug. I have written the QuickSort Algorithm, but it works for small array, but with large array it throws invalid result (last 3-4 elements didn't sort at all).

Test Case 1:

Input: { 5, 7, 2, 8, 10, 15, 14, 16, 16, 19, 20, 19, 3, 1, 5 }

OutPut: 1,2,3,5,10,14,15,16,16,19,20,19,7,5,8 (WRONG)

Test Case 2:

Input: { 5,1,15,2,8}

Output: 1,2,5,8,15

[TestMethod]
    public void QuickSort_test()
    {
        //input
        int[] input = InputArray();


        //Algo
        int n = input.Length-1;
        QuickSort(0,n,input);


        //matching result
        bool isSorted = IsSorted(input);
        Assert.AreEqual(true, isSorted);

    }

    private void QuickSort(int low, int high, int[] arr)
    {
        if(low< high)
        {
            
            //finding pivot correct index
            int idxPivot = Partition(low, high, arr);

            //Recursive QuickSort, on elements left on pivot and elements right on pivot
            int h = high - idxPivot;
            QuickSort(low, idxPivot - 1, arr);        //left of pivot
            QuickSort(idxPivot + 1, h, arr);        //right of pivot
        }            
    }

    private int Partition(int low,  int high, int[] arr)
    {
        int pivot = arr[high];
        int idxp = low - 1; //smaller than pivot            

        for (int i = low; i < high; i++)    //since element at high is already pivot, no need to run loop till that
        {
            if(arr[i]< pivot)  //current ele < pivot . increment pivotsmallerIndex and swap current element with pivot smaller index
                                // hence making current element as the smaller element from pivot
            {                    
                idxp++;
                //swapping
                int temp = arr[idxp];
                arr[idxp] = arr[i];
                arr[i] = temp;

            }
        }

        //idxp contains the last smallest element from the pivot
        //so swapping pivot with the next element of idxp
        int temp1 = arr[idxp + 1];
        arr[idxp+1] = pivot;            
        arr[high] = temp1;

        //return index of pivot, since it is added at idxp+1 now
        return idxp + 1;
    }

 public int[] InputArray()
        {
            return new int[] { 5, 7, 2, 8, 10, 15, 14, 16, 16, 19, 20, 19, 3, 1, 5 };
            //return new int[] { 5,1,15,2,8};

        }
0

There are 0 answers