Problem with Quick Sort Algorithm

Question

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;

   }
}

Do you always get the wrong sort on the same set of the random numbers? If yes, could you please post the set? Also, what is "int n" parameter in the quicksort(..) method? — VoodooChild
– VoodooChild, Commented Jun 26, 2010 at 2:52

Alex Martelli · Accepted Answer · 2010-06-26 03:08:23Z

8

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

answered Jun 26, 2010 at 3:08

Alex Martelli

887k175 gold badges1.3k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

paxdiablo · Accepted Answer · 2010-06-26 13:12:24Z

3

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.

edited Jun 26, 2010 at 13:12

answered Jun 26, 2010 at 3:12

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

3 Comments

Lisa Over a year ago

This isn't a Homework, but I need the code for my own project.

paxdiablo Over a year ago

Why? If you're using the C# language, use it. Don't re-invent the wheel, that's just crazy talk :-)

Lisa Over a year ago

My project is about teaching sorting Algorithms.I'm not re-inventing anything. So, I need to make my own sort method which I can control where to paint and where to wait and so on.

Collectives™ on Stack Overflow

Problem with Quick Sort Algorithm

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related