Due by the end of today by midnight
Currently it's just bubble sort. You're going to improve it.The first part of the output looks like this
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".
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:
Your task is to make it do that.
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:
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.
The program does still take all nine passes thru the array, but at least it's printing out the sorted portion each time.
The outer loop of normal bubble sort is this:
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:
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!
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: