Question: Worst-case performance of QuickSort can be either O(n^2) or O(n log n), depending on how you choose the pivot. The purpose of this assignment is

Worst-case performance of QuickSort can be either O(n^2) or O(n log n), depending on how you choose the pivot. The purpose of this assignment is to investigate this more deeply. Starting with our QuickSort code (not any other code), measure its performance on random arrays and arrays that are already sorted in either ascending or descending order. You can re-use the own code from previous Assignment. Then, modify the QuickSort code to choose the pivot more carefully. (Note that in several parts of the quickSortStep() code, starting from line 4 of that function, it assumes that the pivot is in the right-most array position. Therefore, one easy way to modify the code is: (1) pick a different pivot location; (2) swap the element at that location with the rightmost array element, to move your pivot to the rightmost position. Then you wont need to change subsequent lines. Again, test your modified code on both random arrays and sorted (ascending and descending) arrays.

QuickSort Code

import javax.swing.JOptionPane; import java.util.Comparator;

public class QuickStort { /** QuickSort method: * Sorts the elements of array arr in nondecreasing order according * to comparator c, using the quick-sort algorithm. Most of the work * is done by the auxiliary recursive method quickSortStep. **/ public static void quickSort (Object[] arr, Comparator c) { if (arr.length < 2) return; // the array is already sorted in this case quickSortStep(arr, c, 0, arr.length-1); // call the recursive sort method } /** QuickSortStep method: * Method called by QuickSort(), which sorts the elements of array s between * indices leftBound and rightBound, using a recursive, in-place, * implementation of the quick-sort algorithm. **/ private static void quickSortStep (Object[] s, Comparator c, int leftBound, int rightBound ) { if (leftBound >= rightBound) return; // the indices have crossed Object temp; // temp object used for swapping // Set the pivot to be the last element Object pivotValue = s[(rightBound + leftBound)/2]; // Now partition the array int upIndex = leftBound; // will scan rightward, 'up' the array int downIndex = rightBound-1; // will scan leftward, 'down' the array while (upIndex <= downIndex) { // scan right until larger than the pivot while ( (upIndex <= downIndex) && (c.compare(s[upIndex], pivotValue)<=0) ) upIndex++; // scan leftward to find an element smaller than the pivot while ( (downIndex >= upIndex) && (c.compare(s[downIndex], pivotValue)>=0)) downIndex--; if (upIndex < downIndex) { // both elements were found temp = s[downIndex]; s[downIndex] = s[upIndex]; // swap these elements s[upIndex] = temp; } } // the loop continues until the indices cross int pivotIndex = upIndex; temp = s[rightBound]; // swap pivot with the element at upIndex s[rightBound] = s[pivotIndex]; s[pivotIndex] = temp; // the pivot is now at upIndex, so recursively quicksort each side quickSortStep(s, c, leftBound, pivotIndex-1); quickSortStep(s, c, pivotIndex+1, rightBound); }

public static void main(String[] args) { //String arr[] = {"5", "3", "2", "6"}; String arr[] = {"This", "is","yet", "another", "Boring", "Array", "Sorting", "test"}; JOptionPane.showMessageDialog(null, "Array before sorting: " + array2String(arr)); // quickSort method's first parameter is just the array; // second is a newly created string comparator object (class defined later in this file) quickSort(arr, new StringComparator());

JOptionPane.showMessageDialog(null, "Array after sorting: " + array2String(arr)); }

private static String array2String(String[] a) { String text="["; for (int i=0; i

}

class StringComparator implements Comparator { public int compare(Object ob1, Object ob2) { String s1 = (String)ob1; String s2 = (String)ob2; //return s1.compareTo(s2); // use compareTo for case-sensitive comparison return s1.compareToIgnoreCase(s2); } }

Analysis Code (Previous Assignment Code)

import java.util.Comparator;

public class Analysis {

private static int moves = 0;

private static int compares = 0;

public static void main(String[] args){

String arr[] = {"a", "hello", "x", "w", "q", "h", "d", "p", "a1", "x2", "w2", "q1", "2h", "2d", "3p", "1a",

"3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5",

"n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5",

"3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5",

"q3x", "q2w", "3qq", "qh4", "ad4", "4ap", "3aa", "3ax", "a5w", "q5", "fh5", "fd5", "fp5",