I implemented a standard quicksort and I have a project where I need to improve it. I am trying to make quicksort faster by implementing median of 3 partitioning. I copied codes from trusted educational sites and the code is working, everything is being sorted. The issue is that, the median of 3 partitioning is taking 20 milliseconds to 40 milliseconds more than the standard quicksort. I am sorting 10240000 integers, positive and negative.
Can anybody help me solve this out?
main class
package sorttest;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
public class SortTest {
public static void main(String[] args) throws FileNotFoundException, IOException {
Clock c = new Clock();
int lo = 0;
int hi = 10239999;
sort s = new sort();
Option2 o = new Option2();
int[] NumArray = populate();
/*c.start();
s.quick(NumArray, lo, hi);
double time = c.stop();
System.out.println("Improved quicksort takes " +time);*/
int[] NumArrays = populate();
c.start();
s.quickiSort(NumArrays, lo, hi);
double times = c.stop();
System.out.println("Quicksort takes " + times);
c.start();
o.quickSort(NumArray, lo, hi);
double time = c.stop();
System.out.println("Improved quicksort takes " + time);
/*for (int i =0; i<NumArray.length; i++){
System.out.println(NumArray[i]);
}*/
}
public static int[] populate() throws FileNotFoundException, IOException {
String[] splitArr = split();
int[] arr = new int[10240000];
for (int i = 0; i < splitArr.length; i++) {
int num = Integer.parseInt(splitArr[i]);
arr[i] = num;
}
return arr;
}
public static String[] split() throws FileNotFoundException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\username\\Documents\\year2\\Engeneering Software Development\\cw3\\ints10240000.dat")));
String line;
String[] aList = new String[10240000];
while ((line = reader.readLine()) != null) {
aList = line.split("\\s+");
//String aList = (line.split("\\s+"))); //using whitespace as delimeter to split
}
return aList;
}
}
Standard quicksort
public void quickiSort(int arr[], int begin, int end) {
if (begin < end) {
int partitionIndex = partitionL(arr, begin, end);
quickiSort(arr, begin, partitionIndex - 1);
quickiSort(arr, partitionIndex + 1, end);
}
}
private int partitionL(int arr[], int begin, int end) {
int pivot = arr[end];
int i = (begin - 1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = swapTemp;
return i + 1;
}
Median of 3 quicksort
package sorttest;
public class Option2 {
public void quickSort(int[] theArray, int lo, int hi) {
recQuickSort(theArray, lo, hi);
}
public void recQuickSort(int[] theArray, int left, int right) {
int size = right - left + 1;
if (size <= 3) {
manualSort(theArray, left, right);
} else {
long median = medianOf3(theArray, left, right);
int partition = partitionIt(theArray, left, right, median);
recQuickSort(theArray, left, partition - 1);
recQuickSort(theArray, partition + 1, right);
}
}
public long medianOf3(int[] theArray, int left, int right) {
int center = (left + right) / 2;
if (theArray[left] > theArray[center]) {
swap(left, center, theArray);
}
if (theArray[left] > theArray[right]) {
swap(left, right, theArray);
}
if (theArray[center] > theArray[right]) {
swap(center, right, theArray);
}
swap(center, right - 1, theArray);
return theArray[right - 1];
}
public void swap(int dex1, int dex2, int[] theArray) {
int temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
public int partitionIt(int[] theArray, int left, int right, long pivot) {
int leftPtr = left;
int rightPtr = right - 1;
while (true) {
while (theArray[++leftPtr] < pivot)
;
while (theArray[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr, theArray);
}
}
swap(leftPtr, right - 1, theArray);
return leftPtr;
}
public void manualSort(int[] theArray, int left, int right) {
int size = right - left + 1;
if (size <= 1) {
return;
}
if (size == 2) {
if (theArray[left] > theArray[right]) {
swap(left, right, theArray);
}
return;
} else {
if (theArray[left] > theArray[right - 1]) {
swap(left, right - 1, theArray);
}
if (theArray[left] > theArray[right]) {
swap(left, right, theArray);
}
if (theArray[right - 1] > theArray[right]) {
swap(right - 1, right, theArray);
}
}
}
}
o.quickSortis given an already sorted array. For a fair comparison you need to repopulate it. \$\endgroup\$