Problem with Quick Sort Algorithm

Question

Hey all,

I'm working on a quick sort algorithm in C#, but I'm facing a strange problem which is, among 10 times of executing the algorithm on random numbers, I got 2 or 3 wrong sorting answers.

I mean: this code can sort about 7 out of 10 examples; why? I couldn't figure out what's the problem, can you help me?

  public void quicksort(int[] data, int first, int n)
   { 
       int pivotIndex, n1, n2;
       if (n > 1)
       {
           pivotIndex= partition(data, first, n);
           n1 = pivotIndex-first;
           n2 = n -n1 -1;
           quicksort(data, first, n1);
           quicksort(data, pivotIndex+ 1, n2);
       }
   }

   private int partition(int[] data, int first, int n)
   {
       int t;
       int pivot= data[first], tooBigIndex=first+1, tooSmallIndex=first+n-1;
       while (tooBigIndex<= tooSmallIndex)
       {
        while( (tooBigIndex < n) && (data[tooBigIndex] <= pivot) )
                tooBigIndex++;
       while (data[tooSmallIndex] > pivot) 
            tooSmallIndex--;
           if (tooBigIndex< tooSmallIndex) 
           {
            t = data[tooBigIndex];
            data[tooBigIndex] = data[tooSmallIndex];
            data[tooSmallIndex] = t;
            tooSmallIndex--;
            tooBigIndex++;
           }
       }
       t= data[0];
       data[0]= data[tooSmallIndex] ;
       data[tooSmallIndex]=t;
       return tooSmallIndex;

   }
}

Answer 1

I'm astonished the code you posted ever works -- or even terminates. The test:

(tooBigIndex < n) &&

should clearly be

(tooBigIndex < first + n) &&

and the index in the lines:

   t= data[0];
   data[0]= data[tooSmallIndex];
   data[tooSmallIndex]=t;

should be first, not 0 (making the first line useless, as you could omit it and use pivot in lieu of t in the third line -- but that's a redundancy, the other two are horrible bugs;-).

I think this is all the bugs, but I've only tested on random arrays;-).

Answer 2

If this is a homework question, you should mark it as such so we can target the assistance better (more nudges in the right direction rather than outright solutions).

If it's not homework, you should consider using the IComparable interface with Array.sort(). For integers, which do provide the IComparable interface, you should be able to just use something like:

int[] valArray = new int[6] { 1, 5, 2, 6, 9, 7 };
Array.Sort (valArray);                            // <-- This is all you need.
String s = "";
foreach (int val in valArray)
    s += "," + val;
MessageBox.Show (s.Substring(1));

which results in:

1,2,5,6,7,9

and I'm pretty certain it uses QuickSort under the covers. Re-inventing the wheel is a bad idea, fine for educational purposes but, if the intent is (as you indicate) to just be able to sort an array, use the language-provided features and save yourself the effort.