Question
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
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 * public class StackArrayBased 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 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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started