Having trouble implementing quicksort in c#

I'm having a bit of trouble trying to get this quicksort algorithm to work 100%. As of now, it's getting hung up a bit when it tries to swap 2 numbers that are the same (tried to remedy that as you'll see in the code).

The darn thing is almost there. I'm just not sure what I'm missing. I spent a few hours trying to figure it out to no avail.

I am doing this for class, unfortunately my teacher said he can't help me, since I'm doing generics (for extra credit) and he can only pull of strings or integers in C# (he's mainly a java/c++ teacher....he hasn't been working with c# for very long).

Quicksort static class

class QuickSort<T> where T : IComparable<T>
{
    //No variables or properties, more of a helper class

    //This is the method that will be called by the user.
    //It ties the internal methods into one to sort the
    //array. It needs an array passed into it, As well as
    //the size of the array.
    public static void  QSort(T[] array,int size)
    {
        //If array is empty, or has 1 element, it is sorted.
        //Return immediatly.
        if (size == 1 || size == 0)
        { return; }
        else
        {   
            //Time to sort, pass in the array, the left bounds of 0,
            //and the right bounds of high - 1 (the last element).
            Partition(array, 0, size);
        }
    }

    //This method splits the work area in half, putting lower
    //values left of the pivot, and greater values right of
    //the pivot.
    private static void Partition(T[] array, int lower, int upper)
    {
        //If upper is less 1, then there is no
        //sorting that can be done.
        if ((upper - lower) < 2)
        { return; }

        //Get the right bound -1, to make sure it stays
        //within actual array bounds
        int left = lower;
        int right = upper-1;

        //Set pivot to equal the middle most array. I used this
        //expression because wikipedia mentions it will stop
        //overflow and invalid pivot position that can come
        //with exceptionally large arrays using the basic
        //(a+b)/2 equation.
        int pivot_index = left + (right - left) / 2;
        T pivot = array[pivot_index];

        while (left < right)
        {
            //array[left] < pivot
            while ((array[left].CompareTo(pivot) <= 0) && (left < right))
            {
                left++;
            }
            //array[right] > pivot
            while ((array[right].CompareTo(pivot) >= 0)&& (left < right))
            {
                right--;
            }


            if (left != right)
            {
                Swap(array, left, right);
                left++;
                right--;
            }
        }

            //Send in the lower bound, and the pivot point.
            Partition(array, lower, right);

            //Send in the pivot point as lower bound, and upper
            Partition(array, right+1, upper);

    }


    //This method simply swaps the first position with the second.
    private static void Swap(T[] array, int position1, int position2)
    {
        T tempHolder = array[position1];
        array[position1] = array[position2];
        array[position2] = tempHolder;
    }

}

Main class

class Tester
{
    static void Main(string[] args)
    {

        ContiguousList<int> tester = new ContiguousList<int>(100);
        Random rand = new Random(5433);
        for (int ii = 0; ii < tester.Size; ii++)
        {
            tester.SetElement(ii, rand.Next(0, 100));
        }

        for (int ii = 0; ii < tester.Size; ii++)
        {
            Console.WriteLine(tester.GetElement(ii).ToString());
        }
        Console.WriteLine();



        tester.Sort();
        for (int ii = 0; ii < tester.Size; ii++)
        {
            Console.WriteLine(tester.GetElement(ii开发者_运维问答).ToString());
        }



    }
}

It's proving rather difficult for me since the only online implementations that I can follow are either for c++ (found a good psuedocode explanation that would work if I could use pointers >.<) or their only for sorting integers.

I'm thinking maybe a swap is missing, or my logic for dealing with if array[left] == array[right] is faulty.

(Oh, and don't mind the ContiguousList thing in main...our teacher had us code our own smart array and told us to use that, so we can see how smart arrays work.)

Thanks for any help folks. My brain is really stumped on this one.

--Edit I changed the loops, so one checks >= 0, the other < 0 to get rid of a non-needed check.

--Edit I tweaked it a bit again, now it seems it's almost sorted still,but not quite, my first 10 elements are 1,1,2,3,2,3,6,5,4,5 so somehow someway something is not getting swapped right when the values are the same.

Edit-- Just re-read the quicksort explanation/pseudocode I was using, and noticed a little "this version will only work on arrays with unique elements" warning...so I'm right, in that it has to do when 2 elements hold the same value, something is not working... Stumped on how to fix it atm though >.<

The left element can't be less than the pivot, because of the first loop. And the right element can't be more than the pivot, because of the second loop. So if they are equal, then they must both equal the pivot, and therefore it doesn't matter which half of the array they end up in.

Anyway, I think all you need to do to fix your code is to tweak these lines slightly:

        if (array[left].CompareTo(array[right]) == 0)
        {
            left++;
            right--;
        }
        else if (left != right)
        {
            Swap(array, left, right);
            left++;
            right--;
        }

But there are a couple of simplifications:

1. Because left == right implies array[left].CompareTo(array[right]) == 0), your left != right test is superfluous.
2. As a corollary, you always end up incrementing left and decrementing right. So you can move that outside the conditional.

Thus the resulting code looks like this:

        if (array[left].CompareTo(array[right]) != 0)
        {
            Swap(array, left, right);
        }
        left++;
        right--;

You should change your swap method to swap the actual data, instead of accessing the arrays. In C# you need 'ref' so any data is send along as reference:

    private static void Swap(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }