method to make an almost sorted array into fully sorted. @param arr: an array of integers, with all the numbers are sorted excepted the last one @param size: the number of elements in an array */ public static void insertLast(int[] arr, int size) { // your work } To make it concrete, let's use the example shown in Figure 1. In this example, the array contains [1, 3, 4, 5, 6, 7, 2], and the size of the array is 7. As we can see, The input array are sorted excepted the last one. The goal here is to place last element into a correct position so all numbers will be sorted. This is exactly what the method insertLast is to perform. 1

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question

A method to make an almost sorted array into fully sorted.
@param arr: an array of integers, with all the numbers are sorted
excepted the last one
@param size: the number of elements in an array
*/
public static void insertLast(int[] arr, int size)
{
// your work
}
To make it concrete, let's use the example shown in Figure 1. In this example, the array
contains [1, 3, 4, 5, 6, 7, 2], and the size of the array is 7. As we can see, The input
array are sorted excepted the last one. The goal here is to place last element into a correct
position so all numbers will be sorted. This is exactly what the method insertLast is to
perform.
1
Figure 1: Sampel output for insertion sort part 1.
As we recall from the lecture, the idea is keep shifting all larger number (compared with the
last number) to the right until we nd the number is smaller than the last number. In our
example,
1. Compare 7 with 2. Since 7 > 2, we copy 7 to its right.
2. Compare 6 with 2. Since 6 > 2, we copy 6 to its right.
3. Compare 5 with 2. Since 5 > 2, we copy 5 to its right.
4. Compare 4 with 2. Since 4 > 2, we copy 4 to its right.
5. Compare 3 with 2. Since 3 > 2, we copy 3 to its right.
6. Compare 1 with 2. Since 1 < 2, we stop here and copy 2 to its current position.
In this method, you are required to print the following information for each iteration until
the termination of the loop (See Figure 1):
 The intermediate array content and
 The comparing pair information
In this example, ve numbers (3, 4, 5, 6, and 7) are greater than 2, so you have ve (5)
shifts, and ve lines of outputs, plus one line putting 2 in its right position.
2
2.2 Part2: insertionSort
/**
A method to make an unsorted array into fully sorted.
@param arr: an array of integers
@param size: the number of elements in an array
*/
public static void insertionSort(int[] arr, int size)
{
// your work
}
This method is to make an unsorted array into sorted, which we have discussed in the lec-
ture. The basic idea is to run n ? 1 iterations, and for each iteration, we perform the task
as we implemented in Part 1.
Figure 2: Outputs for part 2: average (Left), best (Middle), and worst (Right) cases
To make it concrete, let's use the example shown in Figure 2 (Left). In this example, the
array contains [5, 7, 3, 6, 4, 1, 2], and the size of the whole array is 7. Since the size
of the array n = 7, you need 6 iterations to get the whole array to be sorted. Particularly,
1. Iteration #1: Perform insertLast on subarray [5, 7]
2. Iteration #2: Perform insertLast on subarray [5, 7, 3]
3. Iteration #3: Perform insertLast on subarray [3, 5, 7, 6]
3
4. Iteration #4: Perform insertLast on subarray [3, 5, 6, 7, 4]
5. Iteration #5: Perform insertLast on subarray [3, 4, 5, 6, 7, 1]
6. Iteration #6: Perform insertLast on subarray [1, 3, 4, 5, 6, 7, 2]
In this method, you are required to print the following information (1) The intermediate
array content and (2) The numbers of shift for each iteration, and the total number of shifts
(See Figure 2).
Important: Since the insertLast prints out intermediate results, you may NOT di-
rectly use this method in insertionSort. You could copy the original source code from
insertLast and disable the printing statements. or write another insertLast method
without printing statements.
2.3 Addtional: printArray
public static void printArray(int [] arr, int size)
A variety of printArray methods with di erent parameters (designed on your own) maybe
useful as you will print out array each iteration used in previous methods.
2.4 main()
To test your program, you may provide a menu list for user to choose (See Figures 1 and 2),
declare an array with the size (given from the keyboard) or xed number, ll up the array val-
ues from the keyboard, invoke one of these two methods (insertLast and insertionSort),
and print out the required formatted program outputs (See Figures 1 and 2).
3 Additional Requirements
1. Your program should not terminate if user does not enter 3 (means terminating the
program). (Hint: you may use do-while loop to control it in your main()).
2. For the testing of part1, make sure you enter an input array with almost sorted,
i.e., all elements in the array are sorted except the last one.
3. For the testing of part 2, you should test your program with the inputs of (a) unsorted
array (average case), (b) sorted array in ascending order (best case), and (c)
sorted array in descending order (worst case). Save screenshots for each case like
I did in Figure 2.
4. Your program should have good style (indentation, whitespace, comments, vertical
alignment, ...).

et Temnal Wndow Prog5 wrtiorot
Opt
Choose the following options
1: Insertion Part #1
2: Insertion Part #2
3: Quit
Enter sorted numbers except the last number, followed by q:
134567 2 9
Detailed shifting outputs:
13 45677
13 45667
13 45567
1344567
133 45 67
1 23 4567
/17 > 2, 7 18 shifted one cell to the right
/16 > 2, 6 1s shifted one cell to the right
//5 > 2, 5 1s shifted one cell to the right
/14 > 2. 4 1s shifted one cell to the right
//3 > 2, 3 is shifted one cell to the right
112 is placed into the right position
rype input and press Enter to send to program
Figure 1: Sampel output for insertion sort part 1.
Choose the tollovang optsons
Choose the felloaing options
Choose the following options
1: Insertion Part a
2: Insertson Part 2
3: Quit
1: Insertion Part a
2: Insertion Part 2
3: Oust
11 Insertion Part
2: Insertion Part 2
3: Quit
Enter a bunch of nuebera followed by a:
5736412a
Enter a bunch of nunbers folloned by a:
Enter a bunch ot nurbers followed by a:
76543214
2345674
Start sorting!
S17 36412 /Original array
5 713 6412 IShafts: e
a5 716 412 IShifta: 2
356 714 1 2
3456 711 2 IShafts: 3
13456 712
123456 71 1/Shafts: 5
Start sorting:
112 34567 11original array
213 4567 1IShafts: e
1 2 314 567 /Shafta: e
123 415 67 1IShifta:
234 516 7 1ISafts:
1 2345 617 ISnafts:
123456 71 1hifta:
Start sertsng:
716 5 4321 /original array
6 715 4 321 /Shifta: 1
56 714 321 IShafte: 2
456713 21
3456 712 1 /Shifts: 4
23456 711
123466 71 1/Shifts: 6
1/Shifte: 1
/Shifts: 3
/Shifta: 5
/Shafts: 5
Total shifta: 16
Total shatts: e
Total shifts: 21
Type anout and press Enter to send to progr
Type input and press Enter to send to pregr
Type inut and press Enter to send to progr
Figure 2: Outputs for part 2: average (Left), best (Middle), and worst (Right) cases
Transcribed Image Text:et Temnal Wndow Prog5 wrtiorot Opt Choose the following options 1: Insertion Part #1 2: Insertion Part #2 3: Quit Enter sorted numbers except the last number, followed by q: 134567 2 9 Detailed shifting outputs: 13 45677 13 45667 13 45567 1344567 133 45 67 1 23 4567 /17 > 2, 7 18 shifted one cell to the right /16 > 2, 6 1s shifted one cell to the right //5 > 2, 5 1s shifted one cell to the right /14 > 2. 4 1s shifted one cell to the right //3 > 2, 3 is shifted one cell to the right 112 is placed into the right position rype input and press Enter to send to program Figure 1: Sampel output for insertion sort part 1. Choose the tollovang optsons Choose the felloaing options Choose the following options 1: Insertion Part a 2: Insertson Part 2 3: Quit 1: Insertion Part a 2: Insertion Part 2 3: Oust 11 Insertion Part 2: Insertion Part 2 3: Quit Enter a bunch of nuebera followed by a: 5736412a Enter a bunch of nunbers folloned by a: Enter a bunch ot nurbers followed by a: 76543214 2345674 Start sorting! S17 36412 /Original array 5 713 6412 IShafts: e a5 716 412 IShifta: 2 356 714 1 2 3456 711 2 IShafts: 3 13456 712 123456 71 1/Shafts: 5 Start sorting: 112 34567 11original array 213 4567 1IShafts: e 1 2 314 567 /Shafta: e 123 415 67 1IShifta: 234 516 7 1ISafts: 1 2345 617 ISnafts: 123456 71 1hifta: Start sertsng: 716 5 4321 /original array 6 715 4 321 /Shifta: 1 56 714 321 IShafte: 2 456713 21 3456 712 1 /Shifts: 4 23456 711 123466 71 1/Shifts: 6 1/Shifte: 1 /Shifts: 3 /Shifta: 5 /Shafts: 5 Total shifta: 16 Total shatts: e Total shifts: 21 Type anout and press Enter to send to progr Type input and press Enter to send to pregr Type inut and press Enter to send to progr Figure 2: Outputs for part 2: average (Left), best (Middle), and worst (Right) cases
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY