Write the following methods for sorting an array of integers( IN JAVA): A (non-r
ID: 3876025 • Letter: W
Question
Write the following methods for sorting an array of integers( IN JAVA):
A (non-recursive) insertion sort method,
A recursive merge sort method,
Two different recursive quick sort methods:
A "plain" recursive quick sort method that chooses as the pivot the first element in the (sub)list to be sorted. Also, the base cases for this plain method are lists of 0 elements and lists of 1 element (since these lists are already sorted, you don't need to do anything to sort them).
A modified recursive quick sort method that uses the median-of-three method (pick the median of the 1st, middle and last element of the sub-array as the pivot) to choose the pivot. Also, the base cases for this modified method are lists of 10 elements or less. Your modified method should sort a list of 10 elements or less directly (i.e., with no recursion) using your insertion sort method.
An error-checking method that makes sure that an array is sorted (by checking that each item (after the first item) is at least as large as the previous item).
Finally, write a main method that reads integers from a file into an array and, with each of the above sorting methods, performs the following steps:
Makes a copy of the input array. Remember to make a separate copy of the array for each sorting call (or else you will be resorting a sorted array!). You can use the System.arraycopy.
Sort a new copy of the array using the sorting method, timing how long the method took (in milliseconds). You can time a method as follows:
Run the error-checking method on the sorted array after you have called the method.
Your output should include the timing of each method, the size of the array sorted and whether the error-checking method found any errors in the output from each method, all with appropriate headers. Thus, your output will look something like the following:
(Use the results of your error-checking method to decide whether to print that a sorting method "successfully" or "unsuccessfully" sorted the array.)
Explanation / Answer
INSERTION SORT METHOD
50,854,540,492,656,345,599,518,325,691,700,6,279,938,937,940,411,949,333,717,992,685,378,652,33,701,66,666,657,232,610,598,342,349,210,828,879,378,216,257,94,957,797,21,909,878,730,711,135,118,259
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.