Quicksort - Optimized version of Quicksort Implement an optimized version quicks

Question

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

Explanation / Answer

java.io.*;

java.util.*;

public class Sort

{

public static void main(String args[])

{

double a[5]={16,11,7,9,18,12};

Sort s=new Sort();

s. insertionSort( a[], 0, 5);

s.getPivot( a[], 0, 5);

private void insertionSort(double[] a, int lo, int hi)

{

for (int i = lo; i <= hi; i++)

for (int j = i; j > lo && less(a[j], a[j-1]); j--)

exch(a, j, j-1);

}

public void exch(double[] a, int i, int j)

{

double t = a[i];

a[i] = a[j];

a[j] = t;

}             

double getPivot(double a[], int l, int h)

{

   double mid = (l + h)/2;

   if(a[mid] > a[mid + 1])

     return mid;

   if(a[l > a[mid])

     return getPivot(a, l, mid-1);

   else

    return getPivot(a, mid + 1, h);    

}

}//main

}class

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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