A08

Due Date: Thursday, November 19
File(s) to be submitted: Shaker.java
Sample Output: SampleOutput.html
Starter Files:

• Common.java
• Shaker.java

More Improvements on BubbleSort

Summary

This week you will program an improved version of bubble sort that's called shaker sort. This version sorts arrays of int values.

Details

In L07 we made an improvement to bubble sort. The idea was to notice where the last swap occurred and update the loop bounds accordingly.

That improved version of bubble sort, however, would give no benefit when sorting this array:

Shaker sort aims to improve the performance by bubbling small items toward the front as well as large items toward the rear. The method alternates between pushing a large value up and pushing a small value down:

In the first pass the 10 is pushed to the end of the list. In the second pass the 1 is pushed up to the front. At this point the array is sorted (tho' shaker sort needs to take one more pass thru in order to notice that). Consider, for example, the list we sorted in L07. Shaker sort's first two passes (one up, one down) would give this:

Noter that the unsorted part truly is unsorted, and shaker sort will need two more passes (one up, one down) to make it sorted.

At this point shaker sort can deduce that the array is sorted without doing any more passes: the "unsorted" part is only one space long, and so it must actually be sorted (no list of length one can be unsorted).

So here is how shaker sort works:

• It tracks the beginning and end of the "unsorted" part of the array.
• It does one pass up and then one pass down, and repeats the process until the unsorted part is length one (or less).
• On each pass (up / down) it compares two adjacent elements and swaps them if they're out of order (just like bubble sort).
• On the pass up it notes the last swap position and updates the end of the unsorted part approrpiately.
• On the pass down it notes the last swap position and updates the beginning of the unsorted part appropriately.

Notes on begin and end

When tracking the beginning and end of (part of) an array, we don't usually point to its first and last elements:

First  Second  Third  Last
 104     -6      1     42

The first element is at index 0; the last element is at index 3.

Instead we track the first element and the one after the last element:

Begin                       End
 104     -6      1     42

The beginning is at index 0; the ending is at "index" 4.

If the whole array is being included, then the beginning is 0 and the ending is the array's length. You can see an example of this in the code for Common::printArray:

public static void printArray(int[] arr) { printArray(arr, 0, arr.length); }

To print out the whole array, we print out the parts from index 0 to the length of the array.

For shakerSort, you want to track the beginning and end of the (possibly) unsorted part of the array. Thus for this unsorted part:

Unsorted part ... 3 2 ... ... ... ... ... ... ...

the beginning is 1 and the ending is 3. The length of the unsorted part is 3 - 1 = 2.

I have given you my BubbleSort program (renamed to Shaker) as a model for the program I want. It produces output similar to what's shown above (and like what's shown in the sample output). The difference being that Common doesn't have a method for printing the front and back of an array, so we'll just print the full array along with the unsorted part:

Make sure that your output is exactly the same as the sample output for the first two arrays. Of course, the random array will show different output each time, and thus will be different from what's shown in the sample output.

Note that for the second array (the totally sorted array), shaker sort makes a pass bubbling down even tho' the array was noted as being totally sorted after the pass bubbling up:

It's not a problem because the pass going down shouldn't do any comparisons. It should start at the top of the unsorted portion of the array, and that's right at the beginning of the array. So really it's reporting a pass bubbling down, but it's not actually doing any work for it.