Bubble sort

The first sort method that is worth investigating is the terrible “bubble” sort.

This is one of the worst sorting methods you could possibly choose but it is simple and it is interesting to see why it is so awful.

There are three simple improvements that can be made to the terrible bubble sort that make it a little better and these can be investigated as options in the Sort Lab.

Add a new button and three RadioButtons. Change their captions to “Sort”, “Reducing” and “Bi-directional”.To make the RadioButtons work as a group set their GroupName to Bubble and set the Sort RadioButton IsChecked property to true:

<Button Content="Bubble Sort" 
 Height="23" 
 Name="button3" 
 Width="75" 
 Click="button3_Click" />
<RadioButton Content="Sort" 
 Height="16" 
 Name="radioButton1" 
 GroupName="Bubble" 
 IsChecked="True" />
<RadioButton Content="Reducing" 
 Height="16" 
 Name="radioButton2" 
 GroupName="Bubble" />
<RadioButton Content="Bi-directional" 
 Height="16" 
 Name="radioButton3" 
 GroupName="Bubble" />

In this case we have to run the actual bubble sort methods in a non-UI thread and again the swap method in the UI thread.

Instead of using the BackgroundWorker thread class as for the shuffle let's implement the threading directly, i.e. create and start threads to do the job.

Let's look in detail at implementing just the simple basic bubble sort. The button click event handler has to call the correct Bubble sort depending on the state of the Radio buttons. As we are focusing on the basic bubble sort the reduced version of the handler is:

private void button3_Click(object sender, 
                RoutedEventArgs e)
{
 if (Working) return;
 Working = true;
 if ((bool)radioButton1.IsChecked)
 {
  Thread T1 = new Thread(
         new ThreadStart(BubbleSimple));
  T1.Start();
 }
}

Notice that all it does is to create and start a thread running the correct bubble sort method.

The bubble sort methods can now be written ignoring the fact that they are being run on a separate thread. To do the data and UI update they simply call swapData:

void BubbleSimple()
{
 bool flag = false;
 do
 {
  flag = false;
  for (int i = 0;i<data.Length - 1;i++)
  {
   if (data[i] > data[i + 1])
   {
    flag = true;
    swapData(i, i + 1);
   }
  }
 } while (flag);
 Working = false;
}

Notice that the one thing that the bubble sort routine has to do is to reset the Working flag to indicate that it has finished.

The key to  being able to ignore the thread that the bubble sort is running on is that the swapData method has to run the UI part of the swap on the UI thread. It starts off much as before:

void swapData(int i,int j)
{
 int t = data[i];
 data[i] = data[j];
 data[j] = t;

With the data swapped it is time to swap the UI components and to do this we need to define a delegate with the correct signature. We can't simply use an anonymous method or a lambda expression in this case because the parameter type is Delegate and this doesn't provide any information about the signature of the method being passed.

The delegate type is just:

delegate void UIswap(int i, int j);

and the actual delegate object is:

UIswap swap= ( i1, j1)=> 
{
 double temp;
 temp = lines[i1].X2;
 lines[i1].X2 = lines[j1].X2;
 lines[j1].X2 = temp;
};

Now we can use the BeingInvoke dispatcher method to run the delegate on the UI thread:

 Deployment.Current.Dispatcher.
     BeginInvoke(swap,
              new object[] { i, j }  );
 Thread.Sleep(1);
}

Notice the way that the parameters are packaged up into an object array as part of the call. Also using the Deployment object to get the current Dispatcher is in theory the only safe way of getting the Dispatcher associated with the UI thread.

An alternative way of doing the same job which is much neater is to define a lambda expression with no parameters and use closure to provide the i,j values as in:

Deployment.Current.Dispatcher.
  BeginInvoke( ()=>   {
    double temp;
    temp = lines[i].X2;
    lines[i].X2 = lines[j].X2;
    lines[j].X2 = temp;
  });

<ASIN:1847199763 >

<ASIN:0470534044 >

<ASIN:0470524650 >

<ASIN:1430230185 >

<ASIN:0672333368 >

<ASIN:1430272074 >