Problem 3 In the programming language of your choice, implement both Insertion Sort and Merge Sort as described in class
Posted: Thu Jul 14, 2022 2:06 pm
Problem 3 In the programming language of your choice, implement both Insertion Sort and Merge Sort as described in class. Feel free base your use implementations that you find online, just ensure that both Merge Sort Insertion Sort implementations operate on similar objects and properly cite your sources. Add code to both algorithms that tracks the time it takes to process an input. You will also need to create a method that generates arrays of integers of various sizes and orderings. (Your submission for this question does not need to contain the code, but you must be able to provide that code upon request)
(a) [10 points] Run your algorithms on various sized lists of random
integers and graph the running time. Does your graph match the theoretical
analysis we did in class, explain why or why not? (Try to get to the point where the slower of the two algorithms finishes in more than one second.)
(b) [10 points] Repeat part (a) using already sorted lists of integers. Graph and explain your results.
(c) [10 points] Choose a list size and experimentally determine the number of array elements that can be out of order before Insertion sort is not longer the faster option. Graph and explain your results.
(a) [10 points] Run your algorithms on various sized lists of random
integers and graph the running time. Does your graph match the theoretical
analysis we did in class, explain why or why not? (Try to get to the point where the slower of the two algorithms finishes in more than one second.)
(b) [10 points] Repeat part (a) using already sorted lists of integers. Graph and explain your results.
(c) [10 points] Choose a list size and experimentally determine the number of array elements that can be out of order before Insertion sort is not longer the faster option. Graph and explain your results.