Worst-case performance of QuickSort can be either O(n^2) or O(n log n), dependin
ID: 3706916 • Letter: W
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 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 won’t need to change subsequent lines. Again, test your modified code on both random arrays and sorted (ascending and descending) arrays. Present your results with a table and plot.
QuickSort 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",
"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",
"n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5",
"q3x", "q2w", "3qq", "qh4", "ad4", "4ap", "3aa", "3ax", "a5w", "q5", "fh5", "fd5", "fp5",
"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",
"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",
"n3x", "2bw", "n3q", "nh4", "nd4", "n4p", "b3a", "b3x", "c5w", "xq5", "kh5", "dj5", "jp5",
"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",
"3x", "2w", "3q", "h4", "d4", "4p", "3a", "3x", "5w", "q5", "h5", "d5", "p5",
"g3x", "g2w", "f3q", "fh4", "gd4", "f4p", "f3a", "d3x", "s5w", "sq5", "sh5", "dd5", "sp5"};
//String arr2[] = (String[])arr.clone();
//String arr3[] = (String[])arr.clone();
//quickSort(arr, new StringComparator());
//insertionSort(arr2);
//shellSort(arr3);
//System.out.println("Quick Sort -------------- Num Comparisons: " + quickCompare + " Num Moves: " + quickMove + " ");
//insertionSort(arr2);
//System.out.println("Insertion Sort -------------- Num Comparisons: " + insertCompare + " Num Moves: " + insertMove + " ");
//insertMove = 0;
//insertCompare = 0;
//shellSort(arr3);
//System.out.println("Shell Sort -------------- Num Comparisons: " + insertCompare + " Num Moves: " + insertMove + " ");
//String[] rand = randomStringArray(10);
//System.out.println(array2String(rand));
Performance(5000);
Performance(10000);
Performance(25000);
//Performance(50000);
//Performance(100000);
}
private static void insertionSort(Comparable[] a, int first, int last, int gap)
{
int index; // general index for keeping track of a position in array
int toSort; // stores the index of an out-of-place element when sorting.
for (toSort = first+gap; toSort <= last; toSort += gap)
{
Comparable toSortElement = a[toSort];
boolean moveMade = false;
index = toSort - gap;
while ((index >= first) && (toSortElement.compareTo(a[index]) < 0))
{
compares++;
// Shuffle elements over to the right, put firstUnsorted before them
a[index+gap] = a[index];
moves++;
index = index - gap;
moveMade = true;
}
if (moveMade) {
//System.out.println("Inserting " + toSortElement + " at pos " + (index+1));
a[index+gap] = toSortElement;
moves++;
}
}
}
public static void insertionSort(Comparable arr[])
{
insertionSort(arr, 0, arr.length-1, 1);
}
public static void shellSort (Comparable[] arr)
{
int last = arr.length-1;
// Begin with gap = half length of array; reduce by half each time.
for (int gap = arr.length/2; gap > 0; gap = gap/2)
{
if (gap % 2 == 0) gap++; // if gap is even, move to next largest odd number
// Apply Insertion Sort to the subarrays defined by the gap distance
for (int first = 0; first < gap; first++) {
insertionSort (arr, first, last, gap);
}
} // end for
} // end shellSort
//QuickSort method:
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:
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];
// 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++;
compares++;
}
// scan leftward to find an element smaller than the pivot
while ( (downIndex >= upIndex) && (c.compare(s[downIndex], pivotValue)>=0)){
downIndex--;
compares++;
}
if (upIndex < downIndex) { // both elements were found
temp = s[downIndex];
s[downIndex] = s[upIndex]; // swap these elements
s[upIndex] = temp;
moves += 3;
}
} // 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;
moves += 3;
// the pivot is now at upIndex, so recursively quicksort each side
quickSortStep(s, c, leftBound, pivotIndex-1);
quickSortStep(s, c, pivotIndex+1, rightBound);
}
/** utility method to return string representation of array of strings */
private static String array2String(String[] a)
{
String text="[";
for (int i=0; i<a.length; i++) {
text += a[i];
if (i<a.length-1)
text += ",";
}
text += "]";
return text;
}
private static String[] randomStringArray(int size){
String[] a = new String[size];
for(int i = 0; i < size; i++){
String d = Double.toString(Math.random());
a[i] = d;
}
return a;
}
//Performs 3 Trials for Each Sorting Algorithm and Averages the Results
public static void Performance(int size){
long shellMoves = 0;
long shellCompares = 0;
long quickMoves = 0;
long quickCompares = 0;
long insertMoves = 0;
long insertCompares = 0;
String[] shell1 = randomStringArray(size);
String[] shell2 = (String[])shell1.clone();
String[] shell3 = (String[])shell1.clone();
String[] quick1 = (String[])shell1.clone();
String[] quick2 = (String[])shell1.clone();
String[] quick3 = (String[])shell1.clone();
String[] insert1 = (String[])shell1.clone();
String[] insert2 = (String[])shell1.clone();
String[] insert3 = (String[])shell1.clone();
long startTime = System.currentTimeMillis();
shellSort(shell1);
long endTime = System.currentTimeMillis();
long shellTrial1Time = endTime - startTime;
shellMoves += moves;
shellCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
shellSort(shell2);
endTime = System.currentTimeMillis();
long shellTrial2Time = endTime - startTime;
shellMoves += moves;
shellCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
shellSort(shell3);
endTime = System.currentTimeMillis();
long shellTrial3Time = endTime - startTime;
shellMoves += moves;
shellCompares += compares;
moves = 0;
compares = 0;
shellMoves /= 3;
shellCompares /= 3;
startTime = System.currentTimeMillis();
quickSort(quick1, new StringComparator());
endTime = System.currentTimeMillis();
long quickTrial1Time = endTime - startTime;
quickMoves += moves;
quickCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
quickSort(quick2, new StringComparator());
endTime = System.currentTimeMillis();
long quickTrial2Time = endTime - startTime;
quickMoves += moves;
quickCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
quickSort(quick3, new StringComparator());
endTime = System.currentTimeMillis();
long quickTrial3Time = endTime - startTime;
quickMoves += moves;
quickCompares += compares;
moves = 0;
compares = 0;
quickMoves /= 3;
quickCompares /= 3;
startTime = System.currentTimeMillis();
insertionSort(insert1);
endTime = System.currentTimeMillis();
long insertionTrial1Time = endTime - startTime;
insertMoves += moves;
insertCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
insertionSort(insert2);
endTime = System.currentTimeMillis();
long insertionTrial2Time = endTime - startTime;
insertMoves += moves;
insertCompares += compares;
moves = 0;
compares = 0;
startTime = System.currentTimeMillis();
insertionSort(insert3);
endTime = System.currentTimeMillis();
long insertionTrial3Time = endTime - startTime;
insertMoves += moves;
insertCompares += compares;
moves = 0;
compares = 0;
insertMoves /= 3;
insertCompares /= 3;
long averageShellTime = (shellTrial1Time + shellTrial2Time + shellTrial3Time) / (3);
long averageQuickTime = (quickTrial1Time+ quickTrial2Time + quickTrial3Time) / (3);
long averageInsertionTime = (insertionTrial1Time+ insertionTrial2Time + insertionTrial3Time) / (3);
System.out.println("Average Sorting Algorithm Perfomance for a String Array of size " + size + " Over 3 Trials ====================");
System.out.println("Quick Sort -------------- Num Comparisons: " + quickCompares + " Num Moves: " + quickMoves + " Time: " + averageQuickTime + "ms ");
System.out.println("Insertion Sort -------------- Num Comparisons: " + insertCompares + " Num Moves: " + insertMoves + " Time: " + averageInsertionTime+ "ms ");
System.out.println("Shell Sort -------------- Num Comparisons: " + shellCompares + " Num Moves: " + shellMoves + " Time: " + averageShellTime + "ms ");
}
}
Previous Assignment Code
Previous Assignment Code
Explanation / Answer
Hi.
To find the performance just include few lines of code in the main method where quicksort is applied on the array inputed.
Find the block of code below to check the performance:-
StartTime will store the time just before applying the sorting and StopTime will store the time of system after sorting is applied. The difference between the two times is time taken for quick sort algo to sort the array. The lesser the time the better the performance.
We can include these three lines (startTime, stopTime and elapsedTime) in main to calculate the performance of the code.
You can modify the quicksort by changing the pivot. We can choose any random number or more specifically the mid element in the array as pivot element. But earlier we were choosing the rightmost element as the pivot. So, now just swap the element that you chose as the pivot with the rightmost element, and then partition as before.
i.e.
// Set the pivot to be the last element
Object pivotValue = s[(rightBound + leftBound)/2];
and
int pivotIndex = upIndex+downIndex/2;
Hopeyou got it and this will help you. Thanks!!!Do give this a thumbs up :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.