Download the starter files into a Java project.
Run the program ImprovedBubble.
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
1 2 3 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.
The first change we're going to make
is to change the tracing code
so that it prints out
the sorted part of the array
(that is,
everything from the last swap on).
Here is the tracing code:
if (traceLevel > 0) {
System.out.println("Unsorted part");
Common.printArray(arr, 0, i);
System.out.println("Sorted part");
Common.printArray(arr, i, arr.length);
Common.pause();
}
Introduce a new variable
(lastSwap)
into the bubbleSort method.
Initialize and update it appropriately.
Then modify the tracing code
so that the sorted part of the array gets printed
each pass thru the array:
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
...press enter...
Unsorted part
3 1 2 ... ... ... ... ... ... ...
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
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 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 does still take all nine passes thru the array,
but at least it's printing out the sorted portion each time.
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.
When you're done,
the first part of 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
...press enter...
Unsorted part
3 1 2 ... ... ... ... ... ... ...
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
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...press enter...
The sorted array:
1 2 3 4 5 6 7 8 9 10
...press enter...
An entirely sorted array:
1 2 3 4 5 6 7 8 9 10
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
1 2 3 4 5 6 7 8 9 10
...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.
For example:
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
...press enter...
Unsorted part
224 358 418 467 442 442 ... ... ... ...
Sorted part
... ... ... ... ... ... 678 790 863 995
...press enter...
Unsorted part
224 358 418 442 442 ... ... ... ... ...
Sorted part
... ... ... ... ... 467 678 790 863 995
...press enter...
Unsorted part
... ... ... ... ... ... ... ... ... ...
Sorted part
224 358 418 442 442 467 678 790 863 995
...press enter...
Array now sorted
224 358 418 442 442 467 678 790 863 995
...press enter...