- Activity 1
-
Download the starter files into a Java project.
Run the program QuickSplit.
Give it a list length (perhaps 100),
a maximum value (perhaps 10000),
and a number of pieces (perhaps 5).
The output should look something like this
(but with different randomly-generated numbers):
Quick Split
-----------
A program to find the values that break a sorted list into equal-length pieces,
without actually sorting the list.
Original by Mark Young (A00000000)
Completed by ____ ____ (A00______)
...Press ENTER...
How long should the list be? 100
What should the maximum value be? 10000
How many pieces should it be broken into? 5
...Press ENTER...
Sorting from 0 to 100...
Sorting from 0 to 38...
Sorting from 0 to 23...
Sorting from 0 to 14...
Sorting from 0 to 5...
Sorting from 2 to 5...
Sorting from 6 to 14...
Sorting from 6 to 11...
Sorting from 6 to 9...
Sorting from 12 to 14...
Sorting from 15 to 23...
Sorting from 15 to 17...
Sorting from 18 to 23...
Sorting from 18 to 20...
Sorting from 21 to 23...
Sorting from 24 to 38...
Sorting from 24 to 29...
Sorting from 24 to 26...
Sorting from 27 to 29...
Sorting from 30 to 38...
Sorting from 32 to 38...
Sorting from 32 to 36...
Sorting from 34 to 36...
Sorting from 39 to 100...
Sorting from 39 to 66...
Sorting from 39 to 41...
Sorting from 42 to 66...
Sorting from 42 to 52...
Sorting from 42 to 46...
Sorting from 42 to 44...
Sorting from 47 to 52...
Sorting from 47 to 49...
Sorting from 50 to 52...
Sorting from 53 to 66...
Sorting from 53 to 62...
Sorting from 53 to 58...
Sorting from 55 to 58...
Sorting from 59 to 62...
Sorting from 63 to 66...
Sorting from 67 to 100...
Sorting from 67 to 74...
Sorting from 69 to 74...
Sorting from 71 to 74...
Sorting from 75 to 100...
Sorting from 75 to 80...
Sorting from 77 to 80...
Sorting from 81 to 100...
Sorting from 81 to 92...
Sorting from 81 to 89...
Sorting from 81 to 85...
Sorting from 81 to 83...
Sorting from 86 to 89...
Sorting from 90 to 92...
Sorting from 93 to 100...
Sorting from 93 to 96...
Sorting from 97 to 100...
...Press ENTER...
The 5 pieces are bounded by:
- 1556
- 3473
- 5779
- 7415
...Press ENTER...
For confirmation:
33 47 96 181 200 294 325 359
423 444 497 637 738 842 882 926
1117 1288 1480 1498 ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... 1556 1556 1569 1690
1703 1880 2327 2463 2705 2741 2813 2918
2994 3009 3011 3057 3163 3225 3244 3288
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
3473 3527 3530 3559 3706 3922 3992 4160
4353 4420 4561 4632 4639 4826 5173 5191
5272 5328 5380 5768 ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... 5779 5802 5865 5913
5933 5997 6038 6060 6083 6269 6384 6453
6513 6558 6624 6847 6854 7139 7328 7354
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
7415 7480 7556 7624 7781 7869 7906 7969
7994 8017 8123 8283 8472 8645 8874 9274
9415 9488 9766 9958
...Press ENTER...
- Activity 2
-
Notice that the list (printed out at the end)
is entirely sorted.
That's more work than we actually need to do.
We really only need to find the values
that end up at the "split" points.
In the example above,
those are the values in locations 20, 40, 60 and 80 of the array
(the first value in each printed section after the first).
If you look further up you'll see that the program
reports sorting pieces such as:
- Sorting from 81 to 100...
- Sorting from 81 to 92...
- Sorting from 81 to 89...
- Sorting from 81 to 85...
- Sorting from 81 to 83...
- Sorting from 86 to 89...
- Sorting from 90 to 92...
- Sorting from 93 to 100...
- Sorting from 93 to 96...
- Sorting from 97 to 100...
Again, the numbers you got will almost certainly be different.
None of those sortings needed to happen.
Since we're only looking at the four locations 20, 40, 60 and 80,
all sorting above 80 is work we could have skipped.
Similarly,
all sorting between 21 and 39 is wasted work.
We're going to make a version of the program
that does much less work.
Think about what that would mean
about the "Sorting" messages that get printed out.
Any time that the message doesn't include one of our split points,
that message (and the sorting that goes with it)
can be skipped.
To get an idea of how much work the changes below will save,
try running the original program
with a list of length 1000000, values up to 1000000000, and 10 pieces.
Notice how long it takes to print out the messages.
Do not try to print out the pieces.
That's something that's we can't actually make faster,
and it will be very slow!
- Activity 3
-
Change
printIntoduction
so that it prints your name and A-number
in the place reserved for who completed the program.
Also,
add your name to mine
as an author
in the class javadoc comment.
Do not remove my name,
or forget to add your own (on a separate line
with a separate @author tag).
You will want credit for work that you do,
but you do not want to get a reputation as a credit hog.
Change the names of the QuickSort methods
to QuickSplit.
Add another int[] parameter to those methods.
Call it places.
Change all the calls to a QuickSplit method
to include the places array.
(One method is called once,
and the other is called three times.)
- Activity 4
-
Consider the conditional in the 4-parameter
QuickSplit method:
if (end - begin > 1) {
That says we only need to sort sub-arrays that are of length 2 or more.
Revise it to add a call to a new method:
containsPlace
that has the following javadoc:
/**
* Check whether the given range includes any of the places mentioned in the
* given array.
*
* @param begin the lower bound (inclusive) of the part of the array being
* sorted
* @param end the upper bound (exclusive) of the part of the array being
* sorted
* @param places the list of "interesting" places
* @return true if {@code begin} ≤ {@code places[i]} < {@code end} for any
* value {@code places[i]} in the array {@code places}
*/
The call should ensure that only sub-arrays with "interesting" locations
get sorted.
(Also only sub-arrays of length 2 or more.)
Run your program again to test your code.
You should notice that the number of "Sorting" messages is much smaller
(for example, from 56 above to 17 below).
You should also notice
that the array pieces shown at the end are not entirely sorted,
but that each piece is made up only of numbers less than
(or equal to) the numbers in the next piece.
Run your program multiple times
and check that you only sort pieces that contain an interesting piece,
and that the pieces shown at the end
(except the first)
all start with their smallest value,
which is larger (or equal)
to any value in the previous piece.
Quick Split
-----------
A program to find the values that break a sorted list into equal-length pieces,
without actually sorting the list.
Original by Mark Young (A00000000)
Completed by ____ ____ (A00______)
...Press ENTER...
How long should the list be? 100
What should the maximum value be? 10000
How many pieces should it be broken into? 5
...Press ENTER...
Sorting from 0 to 100...
Sorting from 0 to 48...
Sorting from 0 to 38...
Sorting from 16 to 38...
Sorting from 16 to 24...
Sorting from 16 to 21...
Sorting from 19 to 21...
Sorting from 39 to 48...
Sorting from 39 to 41...
Sorting from 49 to 100...
Sorting from 49 to 81...
Sorting from 49 to 65...
Sorting from 56 to 65...
Sorting from 66 to 81...
Sorting from 72 to 81...
Sorting from 76 to 81...
Sorting from 79 to 81...
...Press ENTER...
The 5 pieces are bounded by:
- 2237
- 4653
- 6604
- 8721
...Press ENTER...
For confirmation:
296 326 407 972 1302 843 1196 1123
1213 785 756 53 1150 298 1184 1374
1638 1401 1690 1890 ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... 2237 2322 2672 2562
2675 3597 3280 3907 4257 4228 3271 4261
3644 4017 2944 3683 3753 3879 4404 4650
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
4653 4819 4866 5225 5140 5154 4973 5164
5534 5602 6152 5729 6027 5928 5858 6268
6401 6500 6347 6372 ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... 6604 7007 7083 6905
7100 7164 7707 7482 7595 7577 7574 7746
8233 8235 7985 8279 8614 8577 8617 8633
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ...
...Press ENTER...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
8721 8817 9276 9434 9066 9686 8965 9304
9391 9634 9895 8915 9131 9883 9603 9594
8870 9871 8879 9603
...Press ENTER...
Remember how we ran the original program with a list of length 1000000?
Try that again with the revised program.
See how much faster it finds the ten required numbers!
Make sure to format your code before you submit it,
and make sure all lines are 80 characters or less long.