title: Having trouble implementing quicksort in c#
body: <p>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).</p>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>Quicksort static class</p>
  
  <pre><code>class QuickSort&lt;T&gt; where T : IComparable&lt;T&gt;
  {
      //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) &lt; 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 &lt; right)
          {
              //array[left] &lt; pivot
              while ((array[left].CompareTo(pivot) &lt;= 0) &amp;&amp; (left &lt; right))
              {
                  left++;
              }
              //array[right] &gt; pivot
              while ((array[right].CompareTo(pivot) &gt;= 0)&amp;&amp; (left &lt; 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;
      }
  
  }
  </code></pre>
  
  <p>Main class</p>
  
  <pre><code>class Tester
  {
      static void Main(string[] args)
      {
  
          ContiguousList&lt;int&gt; tester = new ContiguousList&lt;int&gt;(100);
          Random rand = new Random(5433);
          for (int ii = 0; ii &lt; tester.Size; ii++)
          {
              tester.SetElement(ii, rand.Next(0, 100));
          }
  
          for (int ii = 0; ii &lt; tester.Size; ii++)
          {
              Console.WriteLine(tester.GetElement(ii).ToString());
          }
          Console.WriteLine();
  
  
  
          tester.Sort();
          for (int ii = 0; ii &lt; tester.Size; ii++)
          {
              Console.WriteLine(tester.GetElement(ii).ToString());
          }
  
  
  
      }
  }
  </code></pre>
  
  <p>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 >.&lt;) or their only for sorting integers.</p>
  
  <p>I'm thinking maybe a swap is missing, or my logic for dealing with if array[left] == array[right]  is faulty.</p>
  
  <p>(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.)</p>
  
  <p>Thanks for any help folks. My brain is really stumped on this one.</p>
  
  <p>--Edit
  I changed the loops, so one checks >= 0, the other &lt; 0 to get rid of a non-needed check.</p>
  
  <p>--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.</p>
  
  <p>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 >.&lt;</p>