Quicksort not sorting correctly

Question

Attempting to learn from doing an implementation of Quicksort, I cannot find out why it's not sorting properly.

Using this sequence:

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

It returns this:

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

It seems to sort somewhat, but not all. What have I missed?

Here's 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 your Partition method you have a wrong loop range:

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

Should become:

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

Checkout the related wikipedia article which says:

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

Notice: left ≤ i < right

Answer 2

In addition to my comment on the question itself, I wanted to point out that the Swap() and DoQuickSort() methods do not need to return the array (as per my note in the comment which explains that the array is a reference itself). To that end, your code to do the job should look like the following:

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 3

Are you asking to be handed a fish, or to be taught how to fish?

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

When faced with this problem, the first thing I would do is mark up 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 in here there is a bug. Where? Start listing facts that you believe to be true, and write an assertion for every fact. Write yourself helper methods, like AllLessThan, which verify assertions 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, the moment one of your assertions is violated, you'll get a box that pops up to tell you what the nature of the bug is. Keep doing that, documenting your preconditions and postconditions with assertions until you find the bug.