This assignment gives you opportunities to implement the counting sort, insertion sort, and quicksort algorithms for sorting an integer array in ascending order. You also have an opportunity to revise the quicksort algorithm by using a different method for selecting a pivot and using the insertion sort algorithm to sort a small subarray. You will produce recursive and non-recursive versions of the quicksort algorithm and experience the power of the non-recursive version to sort huge integer arrays.
Doing this assignment will help you develop the ability to understand sorting, to perform runtime analysis of sorting algorithms, and to write and debug well- structured programs of up to 1000 lines of Java code. You can start with the Count- ingSorter class and the InsertionSorter class. Then, continue with the SortClient class without the quicksort. Finally, work on the QuickSorter class and complete the SortClient class. Note that you are not allowed to use Java collections classes other than the Stack class.
Write a class named CountingSorter with a public method that has the following heading.
public static void countingSort(int[] arr)
The method throws an IllegalArgumentException if arr is a null pointer, its length is 0, or it has an element with a negative integer value. The method sorts the given array in ascending order using an algorithm named counting sort. The algorithm starts with setting maxkey to a largest integer in array arr. Then it creates a key- counting array named keycnt of length maxkey + 1 with each element initialized to 0. Next for each index ind of array arr, it increases array keycnt at index arr[ind] by 1 (i.e. performs keycnt[ arr[ind] ]++) so that at the end of this counting pass, keycnt[k] is the number of integer values in array arr that are equal to key k. Finally, for each key k from 0 to maxkey in increasing order, if keycnt[k] is non-zero, save the integer value k in consecutive slots of arr for as many slots as the value of keycnt[k]. The algorithm is illustrated with the following example. Note that you are allowed to use only two arrays in this algorithm: arr and keycnt.
initial contents of arr with 6 values: 2 3 1 2 1 2
maxkey: 3
initial contents of keycnt of length 4: 0 0 0 0
keycnt after performing keycnt[arr[0]]++: 0 0 1 0
keycnt after performing keycnt[arr[1]]++: 0 0 1 1
keycnt after performing keycnt[arr[2]]++: 0 1 1 1
keycnt after performing keycnt[arr[3]]++: 0 1 2 1
final contents of keycnt: 0 2 3 1
indexes (keys) of keycnt: 0 1 2 3
final contents of arr: 1 1 2 2 2 3
arr consists in this order of zero 0, two 1’s, three 2’s and one 3.
Write a class named InsertionSorter with two public methods. The specification of each method is described below.
public static void insertionSort(int[] arr)
The method sorts the given array in ascending order using the insertion sort algorithm. It throws an IllegalArgumentException if arr is a null pointer, or its length is 0. The method calls the method below by passing the entire array, 0, and the length of the array minus 1, respectively as the arguments.
public static void insertionSort(int[] arr, int first, int last)
The method sorts the subarray consisting of positions between first and last (inclusive) using the insertion sort algorithm. The subarray is sorted in ascending order. It throws an IllegalArgumentException if arr is a null pointer, or its length is 0, or first is less than 0, or last is greater than or equal to the length of arr, or first is greater than last.
Write a class named QuickSorter with two public and two private methods. (You are allowed to add private methods although unnecessary.) The specification of each method is given below.
public static int quickSortNonRec(int[] arr, int ps)
The method sorts the given array in ascending order using the non-recursive quick- sort algorithm that keeps a stack of integer pairs and returns the maximum number of integer pairs in the stack. If arr is null, or its length is 0, or ps is less than 2, then throw an IllegalArgumentException. The ps parameter has two roles. First, ps is the size of a pool of candidates from which a pivotal element is selected. This is achieved by passing ps as a parameter to the private partition() method to be described below. Second, if the number of elements in a subarray of arr is less than ps, then the subarray is sorted using the insertion sort algorithm.
The method uses a stack to remember the subarrays that need to be sorted. Pushing a pair of integers start and end onto the stack means that the subarray from index start to index end needs to be sorted in the future. A stack with elements of type Integer is used to save pairs of integers. In other words, the stack is an object of type Stack< Integer >. A pair of integers is saved on the stack by performing two push operations in a row, one integer per push. Similarly, a pair of integers is removed from the stack by performing two pop operations in a row, one integer per pop. Note that a pop operation always removes the last integer that is pushed onto the stack. For example, suppose that you perform the following operations in the given order on a stack object named st: st.push(a), st.push(b), y = st.pop(), and x = st.pop(). Then the effect is to set y to b and x to a.
Initially, the algorithm just pushes onto the stack the pair of integers that represent the entire array. The main body of the algorithm is a while loop conditioned on the stack being not empty. In each iteration of the while loop, the algorithm pops up a pair of integers from the stack. It simply continues with the next iteration if the pair of integers represents a subarray with at most one element. Otherwise, if the number of elements in the subarray is less than ps (in its second role), the algorithm sorts the subarray with the insertion sort algorithm and continue with the next iteration. Otherwise, the algorithm calls the private partition() method with ps (in its first role) as a parameter to partition the subarray into two subarrays to be sorted, and pushes the two corresponding pairs of integers into the stack, and continues with the next iteration. Upon termination of the while loop, the algorithm returns the maximum number of integer pairs that the stack holds over the course of the execution. The maximum number can be computed by comparing the current maximum number with the current number of integer pairs in the stack after integer pairs are pushed onto the stack. The maximum number represents the amount of extra storage space used by the algorithm.
public static void quickSortRec(int[] arr, int ps)
The method sorts the given array in ascending order using the recursive quicksort algorithm. If arr is null, or its length is 0, or ps is less than 2, then throw an Ille- galArgumentException. The method calls the private quickSortRecPriv() method on the entire array with ps as a parameter. The parameter ps has the two roles as described above in the first public method.
private static void quickSortRecPriv(int[] arr, int first, int last, int ps)
The method sorts the subarray consisting of positions first through last using the recursive quicksort algorithm. The subarray is sorted in ascending order. If ps is less than 2, or first is less than 0, or last is greater than or equal to the length of arr, or first is greater than last, then throw an IllegalArgumentException. (Those exceptions are useful in debugging your code.) The parameter ps has the two roles as described above.
The method simply returns if the subarray has one element. If the number of elements in the subarray is less than ps, the method calls the insertion sort algorithm to sort the subarray and returns. Otherwise, the method calls the partition() method with ps as a parameter to get an index mid and recursively sort each of the subarrays from first to mid and from mid + 1 to last. Note that the partition() method ensures that mid is less than last and is greater than or equal to first.
private static int partition(int[] arr, int first, int last, int ps)
The method selects a pivotal element at an index of the subarray from index first to index last and partitions the subarray into two subarrays such that all the elements of subarray 1 are less than or equal to the pivotal element and all the elements of subarray 2 are greater than or equal to the pivotal element. The method returns the rightmost index of subarray 1. The parameter ps is the size of a pool of elements from which a pivotal element is selected. Note that this private method is called by two of the three methods described above.
The method throws an IllegalArgumentException if ps is less than 2, or first is less than 0, or last is greater than or equal to the length of the array, or the number of elements in the subarray is less than ps. The method throws a RuntimeException if the returned index mid (see below) is less than first.
The pivotal element pivot is found by selecting a random subarray range of size ps from index start to index end and sorting the subarray from index start to index end with the insertion sort algorithm and setting the pivotal element pivot to the element at index (start + end) / 2. Here the indexes start and end must satisfy the following conditions: (1) start is greater than or equal to first, (2) end is less than or equal to last, and (3) the number of elements in the subarray from index start to index end is exactly ps. The indexes start and end can be computed as follows. Set limit to last - ps + 1. If limit is greater than first, get a random number r between 0 (inclusive) and limit - first (exclusive), and set start to first + r. Otherwise, set start to first. Then set end to start + ps - 1.
After selecting the pivotal element, the method follows the partition algorithm discussed in class to partition the subarray into two subarrays and returns an index mid between first and last. Subarray 1 runs from index first to index mid, and subarray 2 runs from index mid + 1 to index last. If the partition algorithm discussed in class produces the index mid that is equal to last, set mid to last - 1. The condition happens if and only if the element at last is the pivotal element and the remaining elements in the subarray are less than the pivotal element.
Write a class named SortClient with a main() method to use the methods in the QuickSorter and InsertionSorter classes to sort integer arrays of various sizes and to collect the time (in milliseconds) of each call.
The main() method takes as input four integers from the console. The method first prompts the user to enter the initial size isize of an array to be sorted. Then it prompts the user to enter the parameter ps. Next it prompts the user to enter a parameter seed, which is used as a seed parameter to the Random constructor for generating an array of random integers. Finally it prompts the user to enter a parameter fac, which is used to produce larger array sizes. The values for the four parameters must be at least 2. If the user enters an item that is not an integer or enters an integer that is less than 2, the method needs to handle those exceptions by printing a proper message to the console and waiting for another item. Those exceptions should be handled by using a try-catch structure in a loop.
Next the method performs two applications. In the first application, the method generates an array a1 of length isize with random integers between 0 (inclusive) and isize (exclusive) by calling the nextInt(isize) method from an object of Random class. The parameter seed is used in each call to the Random constructor in the SortClient class. Note that no seed is used in any call to the Random constructor in the other classes. After making a duplicate copy b1 of a1, the method calls InsertionSorter.insertionSort(a1) and QuickSorter.quickSortRec(b1, ps) to sort each array and prints out the running time of each call to System.out in the following format (each call on a separate line):
SortingMethodName ArraySize SortingTimeInMilliseconds
The running time of each call is calculated by taking the difference between the times right before and after the call. The currentTimeMillis() method of System returns the current time in milliseconds (A millisecond is one thousandth of a second). Use long variables to save times.
In the second application, the method obtains a second array size size2 by mul- tiplying isize with fac. It makes three identical arrays a2 and b2 and c2 of length size2 with random integers between 0 (inclusive) and size2 (exclusive). Then it calls CountingSorter.countingSort(a2), QuickSorter.quickSortRec(b2, ps), and QuickSorter.quickSortNonRec(c2, ps), and reports the running time of each call to System.out. For the quickSortNonRec() method, report the maximum num- ber of integer pairs returned by the method as the fourth item on the line. Below are real example lines from the two applications on the console:
Please enter an array size (>= 2): 100000
Please enter a ps integer (>= 2): 10
Please enter a seed integer (>= 2): 31
Please enter a fac integer (>= 2): 100
SortingMethodName ArraySize SortingTimeInMilliseconds DepthOfRecursion
insertionSort 100000 1759
quickSortRec 100000 36
countingSort 10000000 473
quickSortRec 10000000 1728
quickSortNonRec 10000000 2002 26
The recursive quicksort algorithm given in class may suffer from StackOverflowEr- ror if the input array is large and sorted. However, the recursive quicksort algorithm implemented in this assignment is unlikely to suffer from StackOverflowError if the input array is large and sorted, thanks to the use of the random method to select the pivotal element, which often leads to balanced subarrays. The maximum number of integer pairs in the stack gives an upper bound on the maximum number of recursion levels that the recursive version of the quick sort algorithm would take. A small value for this maximum number indicates that the subarrays generated by the method are of balanced sizes, which means that the method is fast and that the recursive version is unlikely to suffer from StackOverflowError.
The sorting methods are tested as follows. In the first application, write and use a private method named isAscending to check if the array sorted by Insertion- Sorter.insertionSort() is indeed in ascending order. If not, throw a RuntimeException. In addition, write and use a private method named isEqual to check if the arrays sorted by InsertionSorter.insertionSort() and QuickSorter.quickSortRec() are equal (i.e. of the same length and have the identical value at each index). If not, throw a RuntimeException.
In the second application, call isAscending to check if the array sorted by Quick- Sorter.quickSortRec() is indeed in ascending order. If not, throw a RuntimeException. In addition, call isEqual to check if the arrays sorted by QuickSorter.quickSortRec() and QuickSorter.quickSortNonRec() are equal, If not, throw a RuntimeException. Also call isEqual to check if the arrays sorted by QuickSorter.quickSortRec() and CountingSorter.countingSort() are equal. If not, throw a RuntimeException.