Help program, in Java Implement an optimized version quicksort algorithm with th
ID: 3833878 • Letter: H
Question
Help program, in Java
Implement an optimized version quicksort algorithm with the following changes: a. Pivot: (i) First element (or any random element) and (ii) median of 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] (ii) insertionsort(a, lo, hi) that sorts 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
A,
import java.util.Comparator;
import java.util.Arrays;
import java.util.Random;
public class Rdmzd_Quick_Sort
{
public static int K = 20;
public static int[] sequence = new int[K];
public static void QuickSort(int lft, int rgt)
{
if (rgt-lft<= 0)
return;
else
{
Random rd = new Random();
int pivotIndex = lft + rd.nextInt(rgt - lft + 1);
swap(pivotIndex, rgt);
int pivot = sequence[rgt];
int partition = partitionIt(lft, rgt, pivot);
QuickSort(lft, partition - 1);
QuickSort(partition + 1, rgt);
}
}
public static int partitionIt(int lft, int rgt, long pivot)
{
int lPtr = lft - 1;
int rPtr = rgt;
while (true)
{
while (sequence[++lPtr] < pivot)
;
while (rPtr > 0 && sequence[--rPtr] > pivot)
;
if (lPtr >= rPtr)
break;
else
swap(lPtr, rPtr);
}
swap(lPtr, rgt);
return lPtr;
}
public static void swap(int d1, int d2)
{
int temp = sequence[d1];
sequence[d1] = sequence[d2];
sequence[d2] = temp;
}
static void printSequence(int[] sorted_sequence)
{
for (int i = 0;i < sorted_sequence.length;i++)
System.out.print(sorted_sequence[i] + " ");
}
public static void main(String args[])
{
System.out.println("Sorting of randomly generated numbers");
Random rdm = new Random();
for (int i = 0; i < K; i++)
sequence[i] = Math.abs(rdm.nextInt(100));
System.out.println(" Original Sequence: ");
printSequence(sequence);
System.out.println(" Sorted Sequence: ");
QuickSort(0, K - 1);
printSequence(sequence);
}
}
public class QkSort {
private static final Random rg = new Random();
private QkSort() {
}
public static <M> void sort(M[] array, Comparator<M> cmp) {
sort(array, cmp, 0, array.length - 1);
}
public static <M> void sort(M[] array, Comparator<M> cmp, int low, int high)
{ if (high > low) {
int pivotIndex = rg.nextInt(high - low) + low;
pivotIndex = partition(array, comp, low, high, pivotIndex);
sort(array, cmp, low, pivotIndex - 1);
sort(array, cmp, pivotIndex + 1, high);
}
}
private static <M> int partition(M[] array, Comparator<M> cmp, int low,
int high, int pivotIndex)
{
M pivot = array[pivotIndex];
swap(array, pivotIndex, high);
int index = low;
for (int i = low; i < high; i++) {
if (comp.compare(array[i], pivot) <= 0)
{ swap(array, i, index);
index++;
} }
swap(array, high, index);
return index;
}
private static <M> void swap(M[] array, int i, int j) {
M temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
Integer[] array = new Integer[15];
Random rg = new Random();
int split = 10;
for (int i = 0; i < split; i++)
{
array[i] = new Integer(rg.nextInt(100));
}
for (int i = split; i < array.length; i++) {
array[i] = null;
}
System.out.println(Arrays.toString(array));
QuickSort.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer 01, Integer 02) {
return 01.compareTo(02);
};
}, 0, split - 1);
System.out.println(Arrays.toString(array));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.