QuickSort C# Implementation

Question

It has been a while since I've implemented a QuickSort and I wanted to write it down like I remembered.

int MyPartition(List<int> list, int left, int right)
{
 int pivot = list[left];
 while(true)
 {
 while(list[left] < pivot)
 left++;
 while(list[right] > pivot)
 right--;
 if(list[right] == pivot && list[left] == pivot)
 left++;
 if(left < right)
 {
 int temp = list[left];
 list[left] = list[right];
 list[right] = temp;
 }
 else
 {
 return right;
 }
 }
}
void MyQuickSort(List<int> list, int left, int right)
{
 if(list == null || list.Count <= 1)
 return;
 if(left < right)
 {
 int pivotIdx = MyPartition(list, left, right);
 if(pivotIdx > 1)
 MyQuickSort(list, left, pivotIdx - 1);
 if(pivotIdx + 1 < right)
 MyQuickSort(list, pivotIdx + 1, right);
 }
}

Sample usage:

var list = RandomList(1000);
MyQuickSort(list, 0, list.Count - 1);

• Gilad: why do you check if pivotIDX > 1
• CodesInChaos: Your choice of pivot means that if you sort an already sorted list it'll hit the worst case of O(n^2) performance. (Personally I'd use a cryptographically random pivot or an algorithm with fast worst-case performance, to prevent attacks where you're given data designed to provoke worst case performance)

Answer 1

With QuickSort, the complexity always comes down to two things:

• how you deal with equal numbers (duplicates)
• which index you use to return from the partition (left or right)

You need to decide up-front whether the pivot value is going to be in the left partition, or the right partition. If the pivot is going to be in the left, then you need to return left index, and the left partition is values <= the pivot.

In my 'education', all the examples I looked at, and all the implementations I have done since then, have always returned the left index.... and they have always included the pivot in the left side.

There are a number of things that stand out to me in your code:

1. you do not start with the left at left + 1 (you know that list[left] == pivot for the first check...)
2. It is common practice for the 'right' index to start at the length (i.e. to be 1 after the last member).
3. you have odd handling for the duplicate value case
4. you are returning right instead of left
5. you are not swapping the pivot to where it belongs.... The point of the partitioning is that you are supposed to end up with the pivot value where it belongs.
6. you are not checking for left>= right on the increment side of the partition loops

The odd handling of duplicates is because the 'left' loop should be a <= loop, not a < loop:

 while(list[left] <= pivot)
 left++;

and you should get rid of the condition:

 if(list[right] == pivot && list[left] == pivot)
 left++;

You should return left.

Then, in the Recursive call, you have the constant value 1 which you use to test the left-condition.... This is a big bug, because the pivot will only return 0 for the left-most partition. The 1 constant should be left ....

I ended up ideoning your code to play with it. IU shuffled around a lot of the logic.

Have a look...

This is the code that does the sort closer to the way that I expect:

using System;
using System.Collections.Generic;
public class Test
{
 static List<int> RandomList(int size) {
 List<int> ret = new List<int>(size);
 Random rand = new Random(1);
 for (int i = 0; i < size; i++) {
 ret.Add(rand.Next(size));
 }
 return ret;
 }
 static int MyPartition(List<int> list, int left, int right)
 {
 int start = left;
 int pivot = list[start];
 left++;
 right--;
 while(true)
 {
 while(left <= right && list[left] <= pivot)
 left++;
 while(left <= right && list[right] > pivot)
 right--;
 if(left > right)
 {
 list[start] = list[left - 1];
 list[left - 1] = pivot;
 return left;
 }
 int temp = list[left];
 list[left] = list[right];
 list[right] = temp;
 }
 }
 static void MyQuickSort(List<int> list, int left, int right)
 {
 if(list == null || list.Count <= 1)
 return;
 if(left < right)
 {
 int pivotIdx = MyPartition(list, left, right);
 //Console.WriteLine("MQS " + left + " " + right);
 //DumpList(list);
 MyQuickSort(list, left, pivotIdx - 1);
 MyQuickSort(list, pivotIdx, right);
 }
 }
 static void DumpList(List<int> list) {
 list.ForEach(delegate(int val)
 {
 Console.Write(val);
 Console.Write(", ");
 });
 Console.WriteLine();
 }
 public static void Main()
 {
 List<int> list = RandomList(100);
 DumpList(list);
 MyQuickSort(list, 0, list.Count);
 DumpList(list);
 }
}