Quicksort really is quick

Although the bi-directional Shell sort is left as an exercise for the reader it isn’t the last sort method to be added to the project.

The Quicksort method was described in great detail a in another article so I’m not going to go over it all again but I can’t leave it out.

So add button to the form and code the button’s click event handler as

private void button5_Click(object sender,
                       RoutedEventArgs e)
 if (Working) return;
 Working = true;
 Thread T1 = new Thread(
           new ThreadStart(startqsort));
 T1.Start();
}

The startqsort is:

void startqsort()
{
 quicksort(0, data.Length-1);
 Working = false;
}

The Quicksort routine is only slightly modified from the previous article:

void quicksort(int start,int finish)
{
 if (start >= finish) return;
 int L = start;
 int R = finish;
 int pivot = data[
 start + (finish - start) / 2];
 scan(ref L, ref R, pivot);
 while (L != R)
 {
  swapData(L, R);
  if (data[L] == pivot &&
                  data[R] == pivot) L++;
  scan(ref L, ref R, pivot);
 }
 quicksort(start, L - 1);
 quicksort(R + 1, finish);
}

void scan(ref int L,ref int R,int pivot)
{
 while (data[L] < pivot)
 {
  L++;
  if (L == R) return;
 }
 while (data[R] > pivot)
 {
  R--;
  if (L == R) return;
 }
}

Now you can watch a Quicksort in action.

Notice the way the scan first sweeps the entire array and then works on smaller sections. Also notice the way that the pivot hops around. No matter how long you look at the resulting animation you can’t help but be impressed by first how fast the Quicksort runs, how it induces global order very quickly and how it makes very good use of it at every stage.

Some conclusions

You can continue to add sorting routines to the lab and you can add additional options to vary how it all works.

What is interesting is that implementing these standard algorithms with some coded animation reveals the problems in creating a good Silverlight app. You can't simply put everything in the UI thread. The BackgroundWorker approach to multi-threading seems good at first but it quickly becomes over complex compared to the direct approach.

Silverlight lacks a fully developed Dispatcher class and this makes it very difficult to create complex synchronizations. In particular the lack of Invoke means that you cannot easily create a sensible producer consumer relationship between the non-UI and UI thread. The best solution for the moment is to use the SynchronizationContext class and its Despatcher oriented derivative.

To access the code for this project, once you have registered,  click on CodeBin.

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

<ASIN:1847199763 >

<ASIN:0470534044 >

<ASIN:0470524650 >

<ASIN:1430230185 >