Quicksort-Optimized version of Quicksort Implement an optimized version quicksor

Question

Quicksort-Optimized version of Quicksort Implement an optimized version quicksort algorithm with the following changes: a. Pivot: (i) First element (or any random element) and a[left], a[center], and a[right] of the subarray (or any three random elements in the subarray) b. Cutoff to insertion sort for subarrays with less than M elements from 0 to 30. You need to add the following two methods: (i) getPivot(a, lo, hi) method that returns the pivot element based on your chosen strategy in the subarray [a[lo, hi] Empirically determine the value M for which value of quicksort runs fasted in your environment to sort random arrays of N doubles, for N = 10^3, 10^4, 10^5, and 10^6. Plot the average running times for M from 0 to 30.

Explanation / Answer

import java.util.Random;

public class QSortAnalysis {

   public QSortAnalysis(int N) {
       Random random = new Random(System.currentTimeMillis());
      
       /*
       * Array with random elementts
       */
       int[] array = new int[N];
       int[] dupArray = new int[N];
       for (int k=0; k<N; k++) {
           dupArray[k] = random.nextInt();
       }
      
       for(int M=0; M<=30; M++) {
           copyFrom(dupArray, array, N);
          
           QSort qSort = new QSort(M);
          
           long startTS = System.currentTimeMillis();
           qSort.sortMethodOne(array, 0, N-1);
           long totalTimeOne = (System.currentTimeMillis() - startTS);
          
           startTS = System.currentTimeMillis();
           qSort.sortMethodTwo(array, 0, N-1);
           long totalTimeTwo = (System.currentTimeMillis() - startTS);
          
           System.out.println("For M = " + M);
           System.out.println("Time Taken (Pivot as first element) = " + (totalTimeOne/1000.0) + " seconds");
           System.out.println("Time Taken (Pivot as median of three elments ) =" +(totalTimeTwo/1000.0) + " seconds ");
       }
   }

   public static void copyFrom(int fromArray[], int toArray[], int N) {
       for (int k=0; k<N; k++) {
           toArray[k] = fromArray[k];
       }
   }

   public static void main(String args[]) {
       System.out.println("For N = 1000 ");
       new QSortAnalysis(1000);
      
       System.out.println("For N = 10000 ");
       new QSortAnalysis(10000);
      
/*       System.out.println("For N = 100000 ");
       new QSortAnalysis(100000);
      
       System.out.println("For N = 100000 ");
       new QSortAnalysis(1000000);
*/  
       }
}

class QSort {

   public int M;
  
   public QSort(int M) {
       this.M = M;
   }
  
   /**
   * QuickSort with pivot taken as median of A[low], A[center], A[high]
   */
   public void sortMethodOne(int arr[], int low, int high) {
       if (low < high) {
           int pi = partitionMethodOne(arr, low, high);
           if (pi == -1) {
               return;
           }
           sortMethodOne(arr, low, pi);
           sortMethodOne(arr, pi + 1, high);
       }
   }

   /**
   * Partition method with pivot taken as median of A[low], A[center], A[high]
   */
   public int partitionMethodOne(int array[], int low, int high) {
      
       if (high-low+1 < M) {
           insertionSort(array, low, high);
           return -1;
       }
      
       int pivot = getPivot(array, low, high);
       int i = low - 1, j = high + 1;

       while (true) {
           do {
               i++;
           } while (array[i] < pivot);

           do {
               j--;
           } while (array[j] > pivot);

           if (i >= j) {
               return j;
           }

           swap(array, i, j);
       }
   }

   /**
   * pivot taken as median of A[low], A[center], A[high]
   *
   * @param array
   * @param low
   * @param high
   * @return
   */
   private int getPivot(int array[], int low, int high) {
       int first = low;
       int second = (low+high)/2 < low ? (low+high)/2 : low;
       int third = high;
       int pivot = Math.max(Math.min(array[first], array[second]), Math.min(Math.max(array[first], array[second]), array[third]));
       return pivot;
   }
  

  
   /**
   * QuickSort with pivot taken as first element
   */
   public void sortMethodTwo(int arr[], int low, int high) {
       if (low < high) {
           int pi = partitionMethodOne(arr, low, high);
           if (pi == -1) {
               return;
           }
           sortMethodTwo(arr, low, pi);
           sortMethodTwo(arr, pi + 1, high);
       }
   }

   /**
   * pivot taken as first element
   */
   public int partitionMethodTwo(int array[], int low, int high) {
       if (high-low+1 < M) {
           insertionSort(array, low, high);
           return -1;
       }

       int pivot = getPivot(array, low, high);
       int i = low - 1, j = high + 1;

       while (true) {
           do {
               i++;
           } while (array[i] < pivot);

           do {
               j--;
           } while (array[j] > pivot);

           if (i >= j) {
               return j;
           }

           swap(array, i, j);
       }
   }

  
   /**
   * Insertion sort method
   *
   * @param array
   * @param low
   * @param high
   */
   public static void insertionSort(int array[], int low, int high) {
        for (int j = low; j <=high; j++) {
            int key = array[j];
            int i = j-1;
            while ( (i >= low) && ( array [i] > key ) ) {
                array [i+1] = array [i];
                i--;
            }
            array[i+1] = key;
        }
   }
   /**
   * method to swap two elements in an array
   */
   public void swap(int array[], int i, int k) {
       int temp = array[i];
       array[i] = array[k];
       array[k] = temp;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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