Silverlight Sorting Lab
Written by Ian Elliot   
Tuesday, 12 October 2010
Article Index
Silverlight Sorting Lab
Shuffle
Bubble sort
Synchronization
Reducing bubble, shaker and shell
Speedy Quicksort

Banner

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.

 

Banner


The Minimum Spanning Tree - Prim's Algorithm In Python

Finding the minimum spanning tree is one of the fundamental algorithms and it is important in computer science and practical programming. We take a look at the theory and the practice and discover how [ ... ]



Setting Up Site-To-Site OpenVPN

Setting up a point-to-point VPN is relatively easy but site-to-site is much more complicated involving certificates and more IP addresses than you can count. Find out how to do it using OpenVPN.


Other Projects

<ASIN:1847199763 >

<ASIN:0470534044 >

<ASIN:0470524650 >

<ASIN:1430230185 >

 



Last Updated ( Monday, 30 October 2023 )