what is the analyis and algorithm in steps for \"Analysis of QuickSort Pivots\"
ID: 3709626 • Letter: W
Question
what is the analyis and algorithm in steps for "Analysis of QuickSort Pivots"
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 implementation from Blackboard (not any other implementation), measure its performance on random arrays and arrays that are already sorted in either ascending or descending order.
Then, modify our QuickSort implementation from Blackboard to choose the pivot more carefully. (Refer to Slide 30 of the lecture notes.) 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 implementation 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 implementation on both random arrays and sorted (ascending/descending) arrays. Present your results with a table and plot.
(last assignment was Sorting Algorithm Analysis given below)
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 ");
}
}
-------------------------------------------------------------------
import javax.swing.JOptionPane;
public class InsertSort
{
private static void insertionSort(Comparable[] a)
{
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.
int last = a.length-1;
for (toSort = 1; toSort <= last; toSort++)
{
Comparable toSortElement = a[toSort];
System.out.println("Checking " + a[toSort] + " at pos " + toSort);
boolean moveMade = false; // Minor optimisation, also used in messages displayed
index = toSort - 1;
while ((index >= 0) && (toSortElement.compareTo(a[index]) < 0))
{
// Shuffle elements over to the right, put firstUnsorted before them
System.out.println("Moving forward " + a[index] + " from pos " + index);
a[index+1] = a[index];
index--;
moveMade = true;
}
if (moveMade) {
System.out.println("Inserting " + toSortElement + " at pos " + (index+1));
a[index+1] = toSortElement;
}
else {
System.out.println("Leaving " + toSortElement + " at pos " + (index+1));
}
}
}
/** Main method to test insertionSort */
public static void main(String[] args)
{
String arr[] = {"W","B","Z","Q","M"};
//Integer arr[] = {12, 17, 3, 2000, 2001, 99, 203};
/*
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"};
*/
JOptionPane.showMessageDialog(null, "Array length is "+ arr.length);
JOptionPane.showMessageDialog(null,
"Array before sorting: " + array2String(arr));
insertionSort(arr);
JOptionPane.showMessageDialog(null,
"Array after sorting with Insertion Sort: " + array2String(arr));
System.exit(0);
}
/** Utility method to return string representation of array of strings */
private static String array2String(Object[] a)
{
String text="[";
for (int i=0; i<a.length; i++) {
text += a[i];
if (i<a.length-1)
text += ",";
}
text += "]";
return text;
}
}
---------------------------------------------------------------
import javax.swing.JOptionPane;
public class ShellSort
{
//Sorts equally spaced elements of an array into ascending order.
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
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))
{
// Shuffle elements over to the right, put firstUnsorted before them
a[index+gap] = a[index];
index = index - gap;
moveMade = true;
}
if (moveMade) {
//System.out.println("Inserting " + toSortElement + " at pos " + (index+1));
a[index+gap] = toSortElement;
}
}
}
public static void insertionSort(Comparable arr[])
{
insertionSort(arr, 0, arr.length-1, 1);
}
/** M Madden: Main method to test shellSort */
public static void main(String[] args)
{
String[] arr = {"aa", "xa", "bq", "aq", "sw2", "ph", "pp"};
// we can also use insertionSort directly
String copy2[] = arr.clone();
JOptionPane.showMessageDialog(null, "Array length is "+ copy2.length);
JOptionPane.showMessageDialog(null, "Array before sorting with InsertionSort " + array2String(copy2));
insertionSort(copy2);
JOptionPane.showMessageDialog(null, "After Sorting with InsertionSort: " + array2String(copy2));
String copy[] = arr.clone();
JOptionPane.showMessageDialog(null, "Array before sorting with Shell Sort: " + array2String(copy));
shellSort(copy);
JOptionPane.showMessageDialog(null, "After Shell Sort" + array2String(copy));
System.exit(0);
}
/** M Madden: 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;
}
}
-----------------------------------------------
import javax.swing.JOptionPane;
import java.util.Comparator;
public class QuickSort
{
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
}
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++;
// 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);
}
/** Main method to test QuickSort */
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;
quickSort(arr, new StringComparator());
JOptionPane.showMessageDialog(null, "Array after sorting: " + array2String(arr));
}
/** 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;
}
}
/** Comparator class for case-insensitive comaprison of strings */
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);
}
}
Explanation / Answer
Hi Dear,
Please find my implementation:
This class has been changed to use Random values with swapping .
NOTE: Keep other classes as it is .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.