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 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, 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
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 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, 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
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 9 images
