Question 2:

Write the following methods for sorting an array of integers:

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:

import java.util.*; ... long timestamp; ... timestamp = new Date().getTime(); // call your method here timestamp = new Date().getTime() - timestamp; 

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:

Comp 2140 Assignment 1 January 2018 Sorting with insertion sort, merge sort and quick sort. (Author [your name]) Time for insertion sort: xxxx milliseconds. Insertion sort successfully sorted xxxx elements. Time for the plain merge sort: xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. Time for the plain quick sort(1st element as pivot): xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. Time for the plain quick sort(median of 3 as pivot): xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. The sorting program ended normally. 

(Use the results of your error-checking method to decide whether to print that a sorting method "successfully" or "unsuccessfully" sorted the array.)

I will provide a large input file, called "A1data-Big.txt" a few days before the due date. You must run your program on this input file, as well as the smaller input file (see below). The first line of the file will contain the number of elements to read in (not including the first line). In the meantime, you can use the smaller input file "A1testData.txt" to get your code working. (You can find both of these files in the "Assignments" section of the course web site.)

 A1testData.txt 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