L07

Due by the end of today by midnight

Starter Files:


SUBMIT   /   Submission Summary

Today's Activities

Preliminaries
Download the starter files into a Java project. Run the program ImprovedBubble.
Currently it's just bubble sort. You're going to improve it.
The first part of the output looks like this
Bubble Sort =========== This program demonstrates an improvement to bubble sort. A mostly sorted list: 3 4 5 1 2 6 7 8 9 10 ...press enter... Unsorted part 3 4 1 2 5 6 7 8 9 ... Sorted part ... ... ... ... ... ... ... ... ... 10

Notice that the "Unsorted part" of the list actually has a long part that is sorted: everything from the 5 to the 10 is exactly where it's going to end up. Yet the program continues bubbling along, adding only one item at a time to the "Sorted part".

Unsorted part 3 1 2 4 5 6 7 8 ... ... Sorted part ... ... ... ... ... ... ... ... 9 10 ...press enter... Unsorted part 1 2 3 4 5 6 7 ... ... ... Sorted part ... ... ... ... ... ... ... 8 9 10 ...press enter... Unsorted part 1 2 3 4 5 6 ... ... ... ... Sorted part ... ... ... ... ... ... 7 8 9 10 ...press enter... Unsorted part 1 2 3 4 5 ... ... ... ... ... Sorted part ... ... ... ... ... 6 7 8 9 10 ...press enter... Unsorted part 1 2 3 4 ... ... ... ... ... ... Sorted part ... ... ... ... 5 6 7 8 9 10 ...press enter... Unsorted part 1 2 3 ... ... ... ... ... ... ... Sorted part ... ... ... 4 5 6 7 8 9 10 ...press enter... Unsorted part 1 2 ... ... ... ... ... ... ... ... Sorted part ... ... 3 4 5 6 7 8 9 10 ...press enter... Unsorted part 1 ... ... ... ... ... ... ... ... ... Sorted part ... 2 3 4 5 6 7 8 9 10 ...press enter... The sorted array: 1 2 3 4 5 6 7 8 9 10

The program would run so much faster if it noticed that no swaps occurred after the 5. In the very first pass thru the list, the 5 got pushed past the 1 and the 2, then bumped into the 6. There were no more swaps in the rest of that pass. That means that everything from the 5 on is sorted.

We can improve bubble sort by getting it to notice things like that. For example, the output of the program could have been:

Bubble Sort =========== This program demonstrates an improvement to bubble sort. A mostly sorted list: 3 4 5 1 2 6 7 8 9 10 ...press enter... Unsorted part 3 4 1 2 ... ... ... ... ... ... Sorted part ... ... ... ... 5 6 7 8 9 10

Your task is to make it do that.

Activity 1
Introduce a new variable lastSwap that says where the last swap in the array was on each pass thru the array, and print it out at the bottom of the loop. The output for the first two passes thru the loop should look like this:
Bubble Sort =========== This program demonstrates an improvement to bubble sort. A mostly sorted list: 3 4 5 1 2 6 7 8 9 10 ...press enter... Unsorted part 3 4 1 2 5 6 7 8 9 ... Sorted part ... ... ... ... ... ... ... ... ... 10 Last swap was from position 3 to position 4. ...press enter... Unsorted part 1 2 3 4 5 6 7 8 ... ... Sorted part ... ... ... ... ... ... ... ... 9 10 Last swap was from position 2 to position 3. ...press enter...
Activity 2
The next change is to make the tracing code print out the parts of the array before and after the "last swap" position.

Find the code that prints out the two parts of the array, and modify it to use the last swap position instead of the loop control variable.

A mostly sorted list: 3 4 5 1 2 6 7 8 9 10 ...press enter... Unsorted part 3 4 1 2 ... ... ... ... ... ... Sorted part ... ... ... ... 5 6 7 8 9 10 Last swap was from position 3 to position 4. ...press enter... Unsorted part 3 1 2 ... ... ... ... ... ... ... Sorted part ... ... ... 4 5 6 7 8 9 10 Last swap was from position 2 to position 3. ...press enter... Unsorted part 1 2 ... ... ... ... ... ... ... ... Sorted part ... ... 3 4 5 6 7 8 9 10 Last swap was from position 1 to position 2. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 Last swap was from position -1 to position 0. ...press enter... The sorted array: 1 2 3 4 5 6 7 8 9 10

The program does still take all nine passes thru the array, but at least it's printing out the sorted portion each time.

Activity 3
We're now going to update the code so that the method avoids all those useless passes.

The outer loop of normal bubble sort is this:

for (int i = arr.length - 1; i > 0; --i)
The inner loop is this:
for (int j = 0; j < i; 0; ++j)
The variable i is used as the upper bound of the inner loop. On the first pass thru the array above, i starts at 9, so j runs from 0 to 8.

Note that for each pass thru the loop, i is the position that we are going to be filling in with the largest remaining (unsorted) value. At the end of the first pass, the value in location 9 is guaranteed to be the largest value in the array.

The normal behaviour of bubble sort is to move the "upper bound" of sorting down by one after each pass thru the array. This works because each pass thru the array is guaranteed to add (at least) one more sorted value to the end of the array. Thus after the first pass thru the array, i is reduced to 8, and j runs from 0 to 7.

What we noticed about the array above is that the first pass thru the array actually added six sorted values to the end of the array (5 to 10, in locations 4 to 9). Since i is the location we're going to be filling in with the largest remaining value, it doesn't need to work its way down thru 8, 7, 6, ..., 4. The next unsorted position is 3. We can make i jump all the way down to 3.

And how do we know that 3 is the value we want? It's because the last swap in this pass was from location 3 to location 4. There were no swaps from location 4 to location 8.

Revise the outer loop so that the unnecessary passes are avoided.

This may involve rewriting the loop control entirely!

When you're done, the program should produce output as follows:

Bubble Sort =========== This program demonstrates an improvement to bubble sort. A mostly sorted list: 3 4 5 1 2 6 7 8 9 10 ...press enter... Unsorted part 3 4 1 2 ... ... ... ... ... ... Sorted part ... ... ... ... 5 6 7 8 9 10 The last swap was from position 3 to position 4. ...press enter... Unsorted part 3 1 2 ... ... ... ... ... ... ... Sorted part ... ... ... 4 5 6 7 8 9 10 The last swap was from position 2 to position 3. ...press enter... Unsorted part 1 2 ... ... ... ... ... ... ... ... Sorted part ... ... 3 4 5 6 7 8 9 10 The last swap was from position 1 to position 2. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 1 2 3 4 5 6 7 8 9 10 The last swap was from position -1 to position 0. ...press enter... The sorted array: 1 2 3 4 5 6 7 8 9 10 ...press enter...

Notice that the mostly sorted list does only four passes thru the array (instead of nine), and the sorted array does only one (also instead of nine).

Make sure you get the exact output shown above.

The program continues by sorting a list of randomly-generated numbers. It's possible that the sorting method will have to do all nine passes, but it's likely to save itself at least one pass, and possibly many.

Here is a sample run. Your numbers (and output) will be different!

Now to try a random list. Enter a trace level: 0 - no tracing 1 - outer loop only 2 - inner loop as well Trace level: 1 358 467 224 418 863 678 442 442 790 995 ...press enter... Unsorted part 358 224 418 467 678 442 442 790 ... ... Sorted part ... ... ... ... ... ... ... ... 863 995 The last swap was from position 7 to position 8. ...press enter... Unsorted part 224 358 418 467 442 442 ... ... ... ... Sorted part ... ... ... ... ... ... 678 790 863 995 The last swap was from position 5 to position 6. ...press enter... Unsorted part 224 358 418 442 442 ... ... ... ... ... Sorted part ... ... ... ... ... 467 678 790 863 995 The last swap was from position 4 to position 5. ...press enter... Unsorted part ... ... ... ... ... ... ... ... ... ... Sorted part 224 358 418 442 442 467 678 790 863 995 The last swap was from position -1 to position 0. ...press enter... Array now sorted 224 358 418 442 442 467 678 790 863 995 ...press enter...

Make sure to format your code to fix the indenataion and spacing, and make sure all lines are 80 characters or less long.


Submit this/these files:


SUBMIT   /   Submission Summary