Shuffle

Next we need to implement the “Shuffle” to give our sort routines something to do.

Programmers often get worried about how to make an ordered list into a random list and there are some truly terrible algorithms for doing it. The simplest I can think of is the sequential shuffle.

All you do is start a sequential scan from the top of the list and for each element generate a random index within the list. Then simply swap the current item with the one at the random index. When you finish the scan you can guarantee that every element in the list has been sent to a random location. If you don’t think that this is random enough, it is, then click the “Shuffle button again.

The algorithm for the sequential shuffle is easy enough - a single for loop and a random swap. However we really need to place the work on a non-UI thread. However the swap isn't only going to update the data array - it is also going to update the chart i.e. the UI. So we ned to run the shuffle on a non-UI thread but swap on the UI thread.

There are a number of ways of doing this but the one option that completely avoids the need to think about threads is to use the BackgroundWorker class. This has three events and event handlers - one runs on a non-UI thread and the other two on the UI thread. You can read about the theory of the BackgroundWorker in: Easy UI threading with the BackgroundWorker.

As we are also going to have to avoid the shuffle routine being restarted while it is in the process of running we need a simple global flag to indicate that things are being done to the data.

private Boolean Working = false;

All of the methods that use the data have to honor this flag. This isn't an ideal way of doing things because it means that in the future some other programmer could add a method and forget to test the flag.

Thus all methods that modify the data have to start:

private void button2_Click(object sender,
                       RoutedEventArgs e)
{
 if (Working) return;
 Working = true;

and when the work is complete we have to remember to set Working back to false. However notice that as the work is going to be done by a non-UI thread the work isn't over when the button's click even handler ends.

All the click event handler has to do is set up an instance of the BackgroundWorker:

BackgroundWorker bw = new BackgroundWorker();
bw.WorkerReportsProgress = true;
bw.WorkerSupportsCancellation = false;
bw.DoWork+=new 
          DoWorkEventHandler(randomise);
bw.ProgressChanged+= 
   new ProgressChangedEventHandler(swap);

The DoWorkEventHandler is run on the non-UI thread the ProgresChangedEventHandler is run on the UI thread when the DoWork event handler fires its event.

We still have to define the event handlers.

The BackgroundWorker also has a RunWorkerComplete event which is fired when the DoWork event handler completes. It also runs on the UI thread and it is the place we have to reset the Working flag:

bw.RunWorkerCompleted+=delegate(object s1,
         RunWorkerCompletedEventArgs e1)
{
 Working=false;
};

That is when this event happens is the moment when all the work is complete. Finally we can fire the DoWork event and get the threads computing: 

 bw.RunWorkerAsync();
}

Now we need to write the two event handlers. The randomise event handler is fairly simple.

void randomise(object sender, 
                      DoWorkEventArgs e)
{
 BackgroundWorker bw=
              (BackgroundWorker)sender;
 Random R = new Random();
 for (int i = 0; i < data.Length; i++)
 {
  int j = R.Next(data.Length);
  bw.ReportProgress(1, 
             new swapindex(){i=i,j=j});
 }
}

Notice that it uses the sender parameter to identify the BackgroundWorker object and hence which ReportProgress event to fire. After working out which two items to swap the event handler uses the ReportProgress method to raise the ProgressChangedEvent and this runs the event handler which runs on the UI thread and so can access the UI components: Notice that the call sets the percentage progress parameter to a dummy value - one in this case and passes the real parameters via an object - a struct in this case

public struct swapindex { 
          public int i; public int j;};

The event handler will have to extract the real parameters from the event arguments object:

void swap(object sender, 
             ProgressChangedEventArgs e)
{
 int i = ((swapindex)e.UserState).i;
 int j = ((swapindex)e.UserState).j;

Once the even handler has i and j it proceeds to swap not just the data values but also the Lines in the chart:

void swap(object sender, 
             ProgressChangedEventArgs e)
{
 int i = ((swapindex)e.UserState).i;
 int j = ((swapindex)e.UserState).j;
 int t = data[i];
 data[i] = data[j];
 data[j] = t;

 double temp;
 temp = lines[i].X2;
 lines[i].X2 = lines[j].X2;
 lines[j].X2 = temp;
}

If you think about it for a moment you should be able to see that all that is needed to make the lines appear to move is to swap their "heights" i.e. X2 property.

If you run the program, click Generate and then click Shuffle you should be able to watch the lines shift about as the shuffle proceeds:

<ASIN:1430230606 >

<ASIN:1430225491 >

<ASIN:0672330628 >

<ASIN:1430219505 >

<ASIN:1430229888 >