Quick sort is not sorting correctly

Question

Trying to learn how to implement a Quicksort implementation, I cannot understand why it is not sorting correctly.

Using this sequence:

6, 7, 12, 5, 9, 8, 65, 3

He returns this:

3, 5, 7, 8, 9, 65, 12, 6

It seems that a little, but not all. What did I miss?

Here is my code:

static void Main(string[] args) { QuickSort qs = new QuickSort(); int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 }; foreach (int l in arr) { Console.Write(l + ", "); } int left = 0; int right = arr.Count() - 1; int[] arrr = qs.DoQuickSort(ref arr, left, right); Console.WriteLine("Sorted List: "); foreach (int i in arrr) { Console.Write(i + " "); } Console.ReadLine(); } public int Partition(int[] array, int left, int right, int PivotIndex) { int pivValue = array[PivotIndex]; array = Swap(ref array, PivotIndex, right); int storeIndex = left; for (int i = PivotIndex; i < right-1; i++) { if (array[i] <= pivValue) { array = Swap(ref array, i, storeIndex); storeIndex = storeIndex + 1; } } array = Swap(ref array, storeIndex, right); return storeIndex; } public int[] Swap(ref int[] arr, int first, int second) { int temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; return arr; } public int[] DoQuickSort(ref int[] array, int left, int right) { if (right > left) { int PivIndex = (left + right) / 2; int newPivIndex = Partition(array, left, right, PivIndex); DoQuickSort(ref array, left, newPivIndex - 1); DoQuickSort(ref array, newPivIndex + 1, right); } return array; } 

Answer 1

In addition to my comment on the question itself, I would like to point out that the Swap() and DoQuickSort() methods do not need to return an array (according to my note in a comment that explains that the array is a reference). For this purpose, your code for completing the task should look like this:

 public int Partition(int[] array, int left, int right, int pivotIndex) { int pivValue = array[pivotIndex]; Swap(array, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (array[i] <= pivValue) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, right); return storeIndex; } public void Swap(int[] arr, int first, int second) { int temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; } public void DoQuickSort(int[] array, int left, int right) { if (right > left) { int pivIndex = (left + right) / 2; int newPivIndex = Partition(array, left, right, pivIndex); DoQuickSort(array, left, newPivIndex - 1); DoQuickSort(array, newPivIndex + 1, right); } } 

Answer 2

Are you asking to transfer fish or learn how to fish?

Learning how to debug your own programs, rather than relying on other people to do it for you, is a skill that will serve you in the future.

When you came across this problem, the first thing I would like to do is mark the code with comments indicating the semantic purpose of each section of code:

 // Choose a pivot halfway along the portion of the list I am searching. int PivIndex = (left + right) / 2; // Partition the array so that everything to the left of the pivot // index is less than or equal to the pivot, and everything to // the right of the pivot is greater than or equal to the pivot. int newPivIndex = Partition(array, left, right, PivIndex); // Recursively sort each half. DoQuickSort(ref array, left, newPivIndex - 1); DoQuickSort(ref array, newPivIndex + 1, right); 

OK, now, somewhere there is an error. Where? Start listing the facts that you think are true and write a statement for each fact. Write yourself helper methods, such as AllLessThan, that test statements for you.

 // Choose a pivot halfway along the portion of the list I am searching. int PivIndex = (left + right) / 2; int pivotValue = array[PivIndex]; // Partition the array so that everything to the left of the pivot // index is less than or equal to the pivot, and everything to // the right of the pivot is greater than or equal to the pivot. int newPivIndex = Partition(array, left, right, PivIndex); Debug.Assert(array[newPivIndex] == pivotValue); Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue)); Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue)); // Recursively sort each half. DoQuickSort(ref array, left, newPivIndex - 1); Debug.Assert(IsSorted(array, left, newPivIndex)); DoQuickSort(ref array, newPivIndex + 1, right); Debug.Assert(IsSorted(array, left, right)); 

Now, when you run this program again, when one of your statements is violated, you will get a window that appears to tell you what the nature of the error is. Continue to do this by documenting your premises and postconditions with statements until you find a mistake.

Answer 3

In your Partition method, you have the wrong range of loops:

 for (int i = PivotIndex; i < right-1; i++) 

It should become:

 for (int i = left; i < right; i++) 

Make a related wikipedia article that states:

 function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // Move pivot to end storeIndex := left for i from left to right - 1 // left ≤ i < right if array[i] ≤ pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex 

Note: left ≤ i < right