Implement Iterative Quicksort and compare with a Recursive Version. In this lab you will write a program in Java to implement an iterative version of the Quick Sort algorithm. A skeleton of the code is provided in the QuickSortComparison.java file. Your assignment is to complete the code for the quickSortIterative method. You have been provided with code to generate multiple instances of test data of different sizes and to write out the run times of the iterative and recursive variations of Quicksort. After running the experiments, you should write a brief report containing a comparison plot of the average runtimes of the iterative and recursive versions.

import java.io.File; import java.io.FileNotFoundException; import java.io.PrintWriter; import java.io.UnsupportedEncodingException; import java.util.Random; import java.util.Scanner; import java.util.Stack; /* Lab designed to study and compare runtimes of iterative and recursive * versions of QuickSort algorithm */

public class QuickSortComparison{ static int stack[]; static int top; /** * Partitions an array for quickSort. * @param first is the index of the first element to sort with * first <= last. * @param last is the index of the last element to sort with * first <= last. * @param theArray is the array to be sorted: the element * between first and last (with * first <= last)will be sorted. * @return the index of the pivot element of * theArray[first..last]. Upon completion of the method, this will * be the index value lastS1 such that S1 = * theArray[first..lastS1-1] < pivot theArray[lastS1] == pivot S2 = * theArray[lastS1+1..last] >= pivot */ private static > int partition(E[] theArray, int first, int last) { // tempItem is used to swap elements in the array E tempItem; E pivot = theArray[first]; // reference pivot // initially, everything but pivot is in unknown int lastS1 = first; // index of last item in S1 // move one item at a time until unknown region is empty for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown) { // Invariant: theArray[first+1..lastS1] < pivot // theArray[lastS1+1..firstUnknown-1] >= pivot // move item from unknown to proper region if (theArray[firstUnknown].compareTo(pivot) < 0) { // item from unknown belongs in S1 ++lastS1; tempItem = theArray[firstUnknown]; theArray[firstUnknown] = theArray[lastS1]; theArray[lastS1] = tempItem; } // end if // else item from unknown belongs in S2 } // end for // place pivot in proper position and mark its location tempItem = theArray[first]; theArray[first] = theArray[lastS1]; theArray[lastS1] = tempItem; return lastS1; } // end partition /** * Calls recursive or iterative quicksort functions based on flag variable isIterative * @param array to be sorted * @param low first index of array * @param high last index of array * @param isIterative flag variable */ public static > void quickSort(E[] array, int low, int high, boolean isIterative) { if (isIterative) quickSortIterative(array, low, high) ; else quickSortRecursive(array, low, high) ; } /** * Performs quicksort with recursion * @param array to be sorted * @param low first index of array slice being sorted * @param high last index of array slilce being sorted */ private static > void quickSortRecursive(E[] array, int low, int high) { if (low < high) { int pi = partition(array, low, high); quickSortRecursive(array, low, pi-1); quickSortRecursive(array, pi+1, high); } } /** * pushes item into stack * @param item to be pushed */ private static void push( int item) { stack[++top] = item; } /** * pops the last item in the stack * @return last item in stack */ private static int pop() { return stack[top--]; } /** * Performs quickSort using iteration with the help of a stack * @param array to be sorted * @param low first index of array slice being sorted * @param high last index of array slilce being sorted */ private static > void quickSortIterative(E[] array, int low, int high) { // TO COMPLETE: // Write code to perform quicksort iteratively using the help of StackArrayBased // using the variables: stack and top and // helper functions: push() and pop() // provided in the class } public static void main(String args[]) { int arraySizes[] = {100,1000,10000,100000,1000000}; int nIterations = 10; long avgRunTimesIter[] = new long[arraySizes.length]; long avgRunTimesRec[] = new long[arraySizes.length]; Random randomNumberGenerator = new Random(101); for(int i =0; i

public class StackArrayBased implements StackInterface{ final int MAX_STACK = 50; // maximum size of stack private E items[]; private int top;

public StackArrayBased() { items = (E[]) new Object[MAX_STACK]; top = -1; } // end default constructor

public boolean isEmpty() { return top < 0; } // end isEmpty

public boolean isFull() { return top == MAX_STACK-1; } // end isFull

public void push(E newItem) throws StackException { if (!isFull()) { items[++top] = newItem; } else { throw new StackException("StackException on " + "push: stack full"); } // end if } // end push

public void popAll() { items = (E[]) new Object[MAX_STACK]; top = -1; } // end popAll public E pop() throws StackException { if (!isEmpty()) { return items[top--]; } else { throw new StackException("StackException on " + "pop: stack empty"); } // end if } // end pop

public E peek() throws StackException { if (!isEmpty()) { return items[top]; } else { throw new StackException("Stack exception on " + "peek - stack empty"); } // end if } // end peek } // end StackArrayBased

public interface StackInterface {

public void popAll();

public void push(E newItem) throws StackException;

public E pop() throws StackException; public E peek() throws StackException; } // end StackInterface

public class StackException extends java.lang.RuntimeException { public StackException(String s) { super(s); } // end constructor

private final static long serialVersionUID = 2006L; } // end StackException