The insertion sort was discussed and the implementation was demonstrated in the sorting lecture. In this assignment, you are asked to re-implement the insertion sort (InsertionSort.java),
with additional requirements. Particularly, you need to show:
1. For each iteration, how a number from a unsorted region is placed in the correction
posion in the sorted region;
2. How to make the whole array be sorted based on the previous step, and count the total
number of shifts during the whole insertion sort process.
2 Details of the Program
To complete the whole implementation, you should write at least the following important
methods:
2.1 Part1: insertLast
/**
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 find 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="">
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, five numbers (3, 4, 5, 6, and 7) are greater than 2, so you have five (5)
shifts, and five 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 lecture. 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 directly 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 different 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 fixed number, fill up the array values from the keyboard, invoke one of these two methods (insertLast and insertionSort),
and print out the required formatted program outputs
Extracted text: TeTer h Choose the followang options Choose the following options Choose the following optiona 1: Insertion Part a1 2: Insertion Part #2 3: Quit t: Insertion Part #1 2: Insertion Part 2 3: Qust 1: Insertion Part 2: Insertion Part 2 3: Quit 2 Entera bunch of numbers followed by q: 57364129 2 Enter a bunch of nunbers followed by q: 12345679 2 Enter a bunch of numbers tollowed by q: 76543214 Start sorting: 517 36412 1/Original array 5 713 6 412 1/Shifts: e 35 716 412 //Shifts: 2 356 714 1 2 1IShits: 1 3 456 711 2 //Shifts: 3 13456 712 123456 71 1/Shifts: 5 Start sorting: 112 34567 1 213 4 5 67 12 314 5 67 123 415 6 7 IShifts: 1234 516 7 1/Shafts: e 1 2345 617 /Shafts: e 123456 7 /Shifts: Start sorting 716 5 43 21 6 715 4 3 21 56 714 3 2 1 456 713 21 3456기2 1 2345671T 123 456 71 /Shifts: 6 11original array /original array 1/Shifts: 1 //Shats: e 1/Snafta: e 1/Shifts: 2 1/Shifts: 3 //Shifta: 4 1/Shifts: //Shifte: 5 Total shifta: 16 Total shifts: a Total shifts: 21 Type anput and press Enter to send to progr Type input and prese Enter to send to progr Typ input and preus Entar to send te progr