Implement both the Double Insertion sort and the Improved Bubble sort algorithm by using java on a randomly generated list of N integer Your program should output only the running time. To measure the sorting time, call System.currentTimeMillis() just before and just after the sorting and take the difference. Submit a copy of your code.
Double Insertion Sort is a variation on Insertion Sort that works from the middle of the array out. At each iteration, some middle portion of the array is sorted. On the next iteration, take the two adjacent elements to the sorted portion of the array. If they are out of order with respect to each other, then swap them. Now, push the left element toward the right in the array so long as it is greater than the element to its right. And push the right element toward the left in the array so long as it is less than the element to its left. The
Improved Bubble Sort: One possible improvement for Bubble Sort would be to add a flag variable and a test that determines if an exchange was made during the current iteration. If no exchange was made, then the list is sorted and so the algorithm can stop early. This makes the best-case performance become O(n) (because if the list is already sorted, then no iterations will take place on the first pass, and the sort will stop right there). Modify the Bubble Sort implementation to add this flag and test.
- Implement both the Double Insertion sort and the Improved Bubble sort algorithm by using java on a randomly generated list of N integer Your program should output only the running time. To measure the sorting time, call System.currentTimeMillis() just before and just after the sorting and take the difference. Submit a copy of your code.
- Measure the running time of your program for N = 10000, 20000, 40000, 100000, and 200000. Take the average of at least 3 measures for each value of N.
- Present the results in the following table:
- Plot the results using an Excel chart (of type lines) to present the runtime complexity comparison between the two sorting methods
Step by step
Solved in 5 steps with 3 images