1
\$\begingroup\$

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);
        }
    }
}
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Your benchmark is flawed. The o.quickSort is given an already sorted array. For a fair comparison you need to repopulate it. \$\endgroup\$ – vnp Mar 27 at 22:01
  • \$\begingroup\$ I called int[] NumArray = populate(); before o.quickSort, and it took 35 milliseconds more than quicksort. Is there any other methods to make quicksort faster? \$\endgroup\$ – teddy Mar 28 at 4:03
  • 1
    \$\begingroup\$ Your benchmark is flawed. You need to compare same inputs for both algorithms (now you are sorting the array with quickiSort and passing the sorted array to quickSort). You also need to calculate a median from multiple passes over the same input on same algorithm to minimize effect of "random" OS/JVM events. Also, is the difference even significant? How long does each algorithm take in total? \$\endgroup\$ – TorbenPutkonen Mar 28 at 12:44
  • 1
    \$\begingroup\$ To extend on the suggestion of @TorbenPutkonen, before you worry about the time difference values, you need to first determine if those values are significantly different. To do this, you need two steps: Data generation and analysis. Generating Data: I would recommend independent tests and recording their run times until you have >30 records (a minimum size requirements for a standard distribution to be significant) Once you have your two data sets, you can perform analysis: link has a step by step to performing a simple test. \$\endgroup\$ – DapperDan Apr 1 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.