Data Structure and Algorithm (Quicksort) Please take your time figuring it out b
ID: 3812658 • Letter: D
Question
Data Structure and Algorithm (Quicksort) Please take your time figuring it out because I want an editable source code that can be run in IDE. Good luck and thank you. 2. Quicksort-Optimized version of Quicksort Implement an optimized version quicksort algorithm with the following changes: a. Pivot: First element (or any random element) and (ii) median of alleft], alcenter], 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 allo..hij (ii) insertionsort(a, lo, hi) that sorts the subarray allo..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 102, 10, 105, and 106. Plot the average running times for M from 0 to 30.Explanation / Answer
import java.util.Random;
public class QkSort {
public static void main(String[] args) {
double[] intl1Array = new double[1000];
Random r = new Random();
//Entering random elements to array
for (int i =0;i<1000;i++) {
intlArray[i]=r.nextDouble();
}
//start time of execution
long lstartTime = System.nanoTime();
//Execution with M value 30
lquickSort(intlArray,30);
//stop time of execution
long lstopTime = System.nanoTime();
//Total time for execution
long ExeTime=lstopTime-lstartTime;
System.out.println("For M=30:"+ExeTime);
//Repeating for M=25,20,15,10,5
lstartTime = System.nanoTime();
lquickSort(intlArray,25);
lstopTime = System.nanoTime();
ExeTime=lstopTime-lstartTime;
System.out.println("For M=25:"+ExeTime);
lstartTime = System.nanoTime();
lquickSort(intlArray,20);
lstopTime = System.nanoTime();
ExeTime=lstopTime-lstartTime;
System.out.println("For M=20:"+ExeTime);
lstartTime = System.nanoTime();
lquickSort(intlArray,15);
lstopTime = System.nanoTime();
ExeTime=lstopTime-lstartTime;
System.out.println("For M=15:"+ExeTime);
lstartTime = System.nanoTime();
lquickSort(intlArray,10);
lstopTime = System.nanoTime();
ExeTime=lstopTime-lstartTime;
System.out.println("For M=10:"+ExeTime);
lstartTime = System.nanoTime();
lquickSort(intlArray,5);
lstopTime = System.nanoTime();
ExeTime=lstopTime-lstartTime;
System.out.println("For M=5:"+ExeTime);
//Printing elements in the sorted array
for (double i : intlArray) {
System.out.println(i);
}
}
//Defenition of function lquicksort;
public static void lquickSort(double[] intlArray,int M) {
recQuickSort1(intlArray, 0, intlArray.length - 1,M);
}
public static void recQuickSort1(double[] intlArray, int left1, int right1,int M) {
int size1 = right1 - left1 + 1;
//If siz is less than M doing insertion sort
if (size1 < M)
insertionSort1(intlArray, left1, right1);
else {
//else doing quick sort
double median1 = medianOf31(intlArray, left1, right1);
int partition1 = lpartition(intlArray, left1, right1, median1);
recQuickSort1(intlArray, left1, partition1 - 1,M);
recQuickSort1(intlArray, partition1 + 1, right1,M);
}
}
// Median act as pivot element
public static double medianOf31(double[] intlArray, int left1, int right1) {
int center1 = (left1 + right1) / 2;
if (intlArray[left1] > intlArray[center1])
swap1(intlArray, left1, center1);
if (intlArray[left1] > intlArray[right1])
swap1(intlArray, left1, right1);
if (intlArray[center1] > intlArray[right1])
swap1(intlArray, center1, right1);
swap1(intlArray, center1, right1 - 1);
return intlArray[right1 - 1];
}
public static void swap1(double[] intlArray, int dex1, int dex2) {
double temp = intlArray[dex1];
intlArray[dex1] = intlArray[dex2];
intlArray[dex2] = temp;
}
//Partitioning based on pivot
public static int lpartition(double[] intlArray, int left1, int right1, double pivot) {
int lleftptr = left1;
int lrightptr = right1 - 1;
while (true) {
while (intlArray[++lleftptr] < pivot)
;
while (intlArray[--lrightptr] > pivot)
;
if (lleftptr >= lrightptr)
break;
else
swap1(intlArray, lleftptr, lrightptr);
}
swap1(intlArray, lleftptr, right1 - 1);
return lleftptr;
}
//insertion sort
public static void insertionSort1(double[] intlArray, int left1, int right1) {
int in, out;
for (out = left1 + 1; out <= right1; out++) {
double temp = intlArray[out];
in = out;
while (in > left1 && intlArray[in - 1] >= temp) {
intlArray[in] = intlArray[in - 1];
--in;
}
intlArray[in] = temp;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.