Quicksort not sorting correctly

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

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.

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

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