- Q1 Structured Insertion Sort Your Program Should Be Called Structsort Java And It Should Define A Single Class Structs 1 (43.53 KiB) Viewed 79 times
Q1) Structured Insertion Sort
Your program should be called StructSort. java and it should define a single class, StructSort. It's
main method will consider one argument, the name of a file containing your input data. Input data
should be positive integers separated by spaces.
Your goal is to take a
"structuring pass" over the data before performing a regular insertion sort. Your
structuring pass will look for runs, starting from the beginning of the array and moving left to right.
Whenever you find a run in this manner that is in DESCENDING order you should reverse it. Keep
track of how many times you reverse values in this fashion. Also keep track of any runs in ASCENDING
order of length 4.
When you go to sort your data, make sure you sort it in ASCENDING order.
Take a look at the example output on the next page to see how to present your results and note what
things you have to look out for while writing your code. DebugRunner can be pretty picky, so you want
to make sure you're pretty close. Don't do wasteful swaps or compares. Use the same names in your own
output. Note the use of singular tense when outputting results about a single occurrence of something.
These are just small programming details, but I want to remind you to keep an eye out for details.
Structured Insertion Sort ExampleYou might type: java StructSort inputsl.tatinputs1.txt might look like:56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13The output would look something like:56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13We sorted in INCR orderWe counted O INCR runs of length 4We performed 6 reversals of runs in DESC orderWe performed 24 compares during structuringWe performed 196 compares overallWe performed 225 swaps overall6 9 10 12 13 13 14 15 21 34 47 49 50 54 54 55 56 70 72 73 75 84 95 96 97
Structured Insertion Sort Example
You might type: java StructSort inputsl.tat
inputs1.txt might look like:
56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13
The output would look something like:
56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13
We sorted in INCR order
We counted O INCR runs of length 4
We performed 6 reversals of runs in DESC order
We performed 24 compares during structuring
We performed 196 compares overall
We performed 225 swaps overall
6 9 10 12 13 13 14 15 21 34 47 49 50 54 54 55 56 70 72 73 75 84 95 96 97
- Q1 Structured Insertion Sort Your Program Should Be Called Structsort Java And It Should Define A Single Class Structs 2 (33.85 KiB) Viewed 79 times
Structured Insertion Sort Example You might type: java StructSort inputs1.txt inputs1.txt might look like: 56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13 The output would look something like: 56 49 50 70 21 55 47 12 15 84 10 6 97 96 54 54 72 34 95 13 75 14 9 73 13 We sorted in INCR order We counted 0 INCR runs of length 4 We performed 6 reversals of runs in DESC order We performed 24 compares during structuring We performed 196 compares overall We performed 225 swaps overall 6 9 10 12 13 13 14 15 21 34 47 49 50 54 54 55 56 70 72 73 75 84 95 96 97