Analysis of QuickSort Pivots <how to write the analysis and algorithm (step by s

Question

Analysis of QuickSort Pivots

<how to write the analysis and algorithm (step by step process) for this assignment!!!!!!!!>:

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.

Answer to this assignment:

QuickSort .java

This class has been changed to use Random values with swapping .

Keep other classes as it is .

Outpt after change is shown in the last

import java.util.Comparator;

import javax.swing.JOptionPane;

public class QuickSort {
   /**
   * 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

      // Random Number
       int random = (int) Math.floor(Math.random() * (rightBound - leftBound + 1) + leftBound);
       // Swap last value with random value
       temp = s[leftBound];
       s[leftBound] = s[random];
       s[random] = temp;

       // 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;
       // 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));
   }

   /** : 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);
   }
}

Output:

Average Sorting Algorithm Perfomance for a String Array of size 5000 Over 3 Trials
====================
Quick Sort
--------------
Num Comparisons: 68098
Num Moves: 43998
Time: 10ms

Insertion Sort
--------------
Num Comparisons: 6287273
Num Moves: 6292263
Time: 137ms

Shell Sort
--------------
Num Comparisons: 53449
Num Moves: 81004
Time: 15ms

Average Sorting Algorithm Perfomance for a String Array of size 10000 Over 3 Trials
====================
Quick Sort
--------------
Num Comparisons: 148544
Num Moves: 95280
Time: 43ms

Insertion Sort
--------------
Num Comparisons: 24951373
Num Moves: 24961362
Time: 580ms

Shell Sort
--------------
Num Comparisons: 128271
Num Moves: 188626
Time: 10ms

example of what i want for the analysis and algorithm:

Assignment

Write a Java program that operates as follows:

• User is asked whether they want to compute the area of a square, rectangle or triangle

• Depending on the response, they are asked for additional information and the answer is displayed

• Formulae:

o Area of square: (length of side) * (length of side)

o Area of rectangle: height * width

o Area of triangle: ½ * (length of base) * (height)

Analysis & Algorithm:

1. Start

2. Ask user to enter a number:1 for square; 2 for rectangle; 3 for triangle

a. InputDialog returns string: set return value to input: String

b. Convert input to choice: int

c. If choice not in range 1-3, repeat Step 2

3. Test value of choice:

a. If 1: (i). ShapeType = Square ,(ii). Ask for length of square (convert String to double) or (iii). Area = length * length

b. If 2: (i). ShapeType = Rectangle ,(ii). Ask for length and width or (iii). Area = length * width

c. If 3: (i). ShapeType = Triangle ,(ii). Ask for base and height or (iii). Area = 0.5 * base * height

4. Display: The area of ShapeType is Area

5. End.

Explanation / Answer

import java.util.*;

public class Areas {
  
public static int n;//declaring a static variable

//main method
public static void main(String args[]) {
Scanner reader = new Scanner(System.in); // Reading from System.in
System.out.println("Enter a number:1 for square; 2 for rectangle; 3 for triangle ");
try{
String inputnumber = reader.next(); // from console input
n = Integer.parseInt( inputnumber ); //converting string to int
}
catch (NumberFormatException e){
System.out.println("not a number");
}
System.out.println("entered number"+n);

//reader.close();

if(n==1){

System.out.println("Enter length of square ");
String input = reader.next(); // from console input
double slen = Double.parseDouble(input);
double sarea=slen*slen;   
System.out.println("The area of Square is "+sarea);
  
}
  
if(n==2){
System.out.println("Enter length of rectangle ");
String input1 = reader.next(); // from console input
double rlen = Double.parseDouble(input1);
  
System.out.println("Enter width of rectangle ");
String input2 = reader.next(); // from console input
double rwid = Double.parseDouble(input2);
double rarea=rlen*rwid;   
System.out.println("The area of rectangle is "+rarea);
  
}

if(n==3){

System.out.println("Enter base of triangle ");
String input3 = reader.next(); // from console input
double tbase = Double.parseDouble(input3);
  
System.out.println("Enter height of triangle ");
String input4 = reader.next(); // from console input
double thei = Double.parseDouble(input4);
double tarea=tbase*thei*0.5;   
System.out.println("The area of triangle is "+tarea);
  
}

else{
System.out.println("you entered a different number ,give numbers with in the range");  
}
  
  
}
}

output:

test1:

test2:

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.