Q1) Structured Insertion Sort Your program should be called StrInSort.java and it should define a single...

 

Transcribed Image Text:

Q1) Structured Insertion Sort Your program should be called StrInSort.java and it should define a single class, StrInSort. 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 2. When you go to sort your data, make sure you sort it in DESCENDING 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. Q2) Theory: Qualify This Structuring How did the structuring pass you performed, specifically the reversals chosen, affect swaps and com- parisons? Was anything else affected? Answer in less than 100 words. Q3) Theory: Size of Runs How do you feel the size of the specific runs you recorded (ASCENDING order of length 2) impacted performance? Answer in less than 100 words. Q4) Theory: Doubly Linked Lists What would implementing this as a Doubly Linked List do? How would the specified structuring affect results? Answer in less than 100 words. Structured Insertion Sort Example You might type: java StrInSort inputs 1.txt inputs1.txt might look like: 88 89 4 63 6 67 55 55 73 19 95 35 41 22 50 33 37 94 48 33 25 72 22 87 1 The output would look something like: 88 89 4 63 6 67 55 55 73 19 95 35 41 22 50 33 37 94 48 33 25 72 22 87 1 We sorted in DESC order We counted 6 ASC runs of length 2 We performed 3 reversals of runs in DESC order We performed 24 compares during structuring We performed 175 compares overall We performed 132 swaps overall 95 94 89 88 87 73 72 67 63 55 55 50 48 41 37 35 33 33 25 22 22 19 6 4 1 Q1) Structured Insertion Sort Your program should be called StrInSort.java and it should define a single class, StrInSort. 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 2. When you go to sort your data, make sure you sort it in DESCENDING 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. Q2) Theory: Qualify This Structuring How did the structuring pass you performed, specifically the reversals chosen, affect swaps and com- parisons? Was anything else affected? Answer in less than 100 words. Q3) Theory: Size of Runs How do you feel the size of the specific runs you recorded (ASCENDING order of length 2) impacted performance? Answer in less than 100 words. Q4) Theory: Doubly Linked Lists What would implementing this as a Doubly Linked List do? How would the specified structuring affect results? Answer in less than 100 words. Structured Insertion Sort Example You might type: java StrInSort inputs 1.txt inputs1.txt might look like: 88 89 4 63 6 67 55 55 73 19 95 35 41 22 50 33 37 94 48 33 25 72 22 87 1 The output would look something like: 88 89 4 63 6 67 55 55 73 19 95 35 41 22 50 33 37 94 48 33 25 72 22 87 1 We sorted in DESC order We counted 6 ASC runs of length 2 We performed 3 reversals of runs in DESC order We performed 24 compares during structuring We performed 175 compares overall We performed 132 swaps overall 95 94 89 88 87 73 72 67 63 55 55 50 48 41 37 35 33 33 25 22 22 19 6 4 1

Answer rating: 100% (QA)

Heres a Java implementation for the Structured Insertion Sort java import javaioBufferedReader import javaioFileReader import javaioIOException public ... View the full answer