Question

After running the experiment with the pivot, comment out the line, update the pivot selection to use the median of the first, middle, and last items, and run the experiment.

What line needs to be commented out and how would I update the pivot selection to use the median?

Example.java

package sorting;

import java.io.IOException;
import java.util.Random;
import sorters.QuickSort;

public class Example {

   public static void main(String args[]) throws IOException {
       int n = 100;   // adjust this to the number of items to sort
       int runs = 11;
      
       
       partB(n, runs);

   public static void partB(int n, int runs) {
       int [] data = new int[n];
       QuickSort quicksort = new QuickSort();
      
       labels(runs);
       for (int i = 0; i < runs; i++) {
           randomArray(data);
           quicksort.sort(data);
       }
       System.out.println();
      
   }
  
   public static void labels(int runs) {
       for(int i = 0; i < runs; i++) {
           String label = "Run " + i;
           System.out.printf("%12s ", label);
       }
       System.out.println();      
   }
  
   public static void randomArray(int [] data) {
       Random rand = new Random();      
       for(int j = 0; j < data.length; j++) {
           data[j] = rand.nextInt();
       }  
   }
  
}

QuickSort.java

package sorters;

// note that this class can only sort primitive ints correctly.

public class QuickSort {
  
   private int[] items;
  
   public void sort(int[] items) {
       this.items = items;
      
       long start = System.nanoTime();
       quicksort(0, items.length-1);
       long finish = System.nanoTime();
       //System.out.println(Arrays.toString(items));
       System.out.printf("%12s ", finish-start);
   }
  
   private int partition(int left, int right) {
       int i = left;
       int j = right;
        int temp;
        int pivot = (int) items[(left + right) / 2];
      
      
        while (i <= j) {
           while((int) items[i] < pivot)
               i++;
            while((int) items[j] > pivot)
                j--;
            if(i <= j) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
                i++;
                j--;
            }
        }
        return i;
   }

   private void quicksort(int left, int right) {

       int index = partition(left, right);

        if(left < index - 1)
           quicksort(left, index-1);
        if(index < right)
            quicksort(index, right);
   }
}

Answer 1

Package -- sorting

class

QuickSort.java

code is changed here in this class file below for calculating median and used a findmedian() function and commnetd previous code of finding partition

Steps to find median:

1) take thr first middle and last element in the last

2) sort the 3 elements (can be done using colections.sort())

3) return the middle element and use it as a pivot

example

for let first element be 5 last be 8 and middle be 3

so element 5,8,3 will be passed

and sorted as 3,5,8

and middle element 5 will be returned called as median used as pivot in algorithm

package sorters;

import java.util.ArrayList;
import java.util.Collections;

// note that this class can only sort primitive ints correctly.

public class QuickSort {
  
   private int[] items;
  
   public void sort(int[] items) {
       this.items = items;
      
       long start = System.nanoTime();
       quicksort(0, items.length-1);
       long finish = System.nanoTime();
       //System.out.println(Arrays.toString(items));
       System.out.printf("%12s ", finish-start);
       
                //FOR CHECKING CORRECT OUTPUT AFTER {YOUR REFERENCE}
                /*
                 * for(int i=0;i<items.length;i++) System.out.print(items[i]+" ");
       System.out.println(); */
   }
  
   //function called inside paertition to find pivot value
   private int findMedian(int a,int b, int c)
   {
           //adding all 3 first last and middle value of arraylist 
           ArrayList<Integer> sortedMedian=new ArrayList<Integer>();
           sortedMedian.add(a);
           sortedMedian.add(b);
           sortedMedian.add(c);
           
           //using collection fucntion sorting items in arraylst
           Collections.sort(sortedMedian);
           
           //return midle value now as there are are 3 elements in list always so middle element will always be 1
           //so returning elemet at 1 index{2nd element}
           return sortedMedian.get(1);
   }
   
   private int partition(int left, int right) {
       int i = left;
       int j = right;
        int temp;
        
        //line to be commented before it was middle
        //int pivot = (int) items[(left + right) / 2];
        
        //now it will be median of first last and middle element
        int pivot = findMedian(items[left], items[(left + right) / 2], items[right]);
      
        while (i <= j) {
           while((int) items[i] < pivot)
               i++;
            while((int) items[j] > pivot)
                j--;
            if(i <= j) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
                i++;
                j--;
            }
        }
        return i;
   }

   private void quicksort(int left, int right) {

       int index = partition(left, right);

        if(left < index - 1)
           quicksort(left, index-1);
        if(index < right)
            quicksort(index, right);
   }
}

Package -- sorters

class

Example.java

package sorting;

import java.io.IOException;
import java.util.Random;
import sorters.QuickSort;

public class Example {

   public static void main(String args[]) throws IOException {
       int n = 100;   // adjust this to the number of items to sort
       
       //set value of n to small to check output for less value for debugging
       int runs = 11;
      
       
       partB(n, runs);
   }


   public static void partB(int n, int runs) {
       int [] data = new int[n];
       QuickSort quicksort = new QuickSort();
      
       labels(runs);
       for (int i = 0; i < runs; i++) 
       {
           randomArray(data);
           
                        //FOR CHECKING CORRECT OUTPUT BEFORE {YOUR REFERENCE}
           /*
                         * for(int k=0;k<data.length;k++) System.out.print(data[k]+" ");
                         * System.out.println();
                         */
           
           quicksort.sort(data);
       }
       System.out.println();
      
   }
  
   public static void labels(int runs) {
       for(int i = 0; i < runs; i++) {
           String label = "Run " + i;
           System.out.printf("%12s ", label);
       }
       System.out.println();      
   }
  
   public static void randomArray(int [] data) {
       Random rand = new Random();      
       for(int j = 0; j < data.length; j++) {
           data[j] = rand.nextInt(10);
       }  
   }
  
}

code is well commented for your better understanding

Note: I have also written code to print array values before and after sorting in comments so that you can check validity of median quick sorting answer and also set value of 'n' less like 5 for better readability of output

Output screenshot:

Output screenshot (VALIDATING INPUT/OUTPUT BY Priting array before and after):

here note only input and output and not format of printing

Hope you are able to understand all concepts easily and Please rate the answer