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