Reducing Bubble

The most obvious improvement that can be made to this simple bubble sort is to restrict the scan to just the un-sorted portion of the array. Given that you can see the way that at each scan the next largest element is “bubbled” into its correct position you can also see that after each scan the size of the ordered part of the array increases by exactly one.

Translating this into code gives -

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

Shaker sort

The final bubble sort method is the bi-directional or Shaker sort.

If you watch the bubble sort in action you can see quite easily that one small value stuck at the bottom of the array can keep the scan going right to the bitter end just because it has to be bubbled to the top. An improvement might be to perform a reverse scan after each forward scan. This would sweep small values to the top as quickly as the standard bubble sort sweeps big values to the bottom. This is easy to implement and we might as well retain the “reducing” aspect of the sorting process and draw the lines to show the active portion of the array.

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

This looks like a complicated subroutine but you should be able to see that it is just the reducing bubble sort written twice in opposite directions!

Shell sort

The next sorting method that it is worth adding to the lab is the Shell sort.

This isn’t really one single sorting method but a technique that can be applied to improve many basic sorting methods. When applied to the bubble sort however it makes good sense. The problem with the basic bubble sort is that no matter how hard it tries it only ever moves and element by one place and so it can take many moves for an element to reach its true location. The shell sort increases the range of the moves. If you call a bubble sort a 1-sort because it compares and swaps elements that are 1 unit appear then a D-sort compares and swaps elements that are D units apart.

To shell sort a list you perform a series of sorts of decreasing distance until you finish with a 1-sort and produce a fully sorted list. Usually D is taken to be half the number of elements and it is divided by two at each subsequent sorts, however there is a lot of evidence that binary D values are not the best choice.

To see how Shell sorting speeds up bubble sort add a new frame and a single button to the form. The button’s event handler is simply:

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

and in the code module the Shell routine is:

void Shell()
{
 bool flag = false;
 int Upper = data.Length - 1;
 int Lower = 0;
 int D = (Upper - Lower) / 2;
 do
 {
  flag = false;
  for (int i =Lower;i<=Upper-D;i+=D)
  {
   if (data[i] > data[i + D])
   {
    flag = true;
    swapData(i, i + D);
   }
  }
  if (D == 1) Upper--;
  if (!flag) D = D / 2;
 } while (flag || D!=0);
 Working = false;
}

This is a really interesting sort to watch in action. It starts off looking really good and it produces a “very nearly ordered” array in no time at all. Then it crawls along doing a 1-sort and finishes usually slower than the simple bubble sort! If you look closely you might agree that the reason is that the time for the final 1-sort is set by the time needed to bubble the smallest element to the top of the array. An obvious improvement would be to make the shell sort bi-directional. As they say in all the best books – this is left as a reader exercise!

<ASIN:1430230606 >

<ASIN:1430225491 >

<ASIN:0672330628 >

<ASIN:1430219505 >

<ASIN:1430229888 >