TestQuicksort.java

import java.util.Random;
import java.util.Arrays;

public class TestQuicksort {

    /**
    *   Program:    TestQuicksort.java
    *   Purpose:    Test quicksort algorithm by applying it to a shuffled array.
    *   Creator:    Chris Clarke
    *   Created:    07.02.2014
    *   Modified:   07.12.2014 - added NanoTimer; added bubblesort for comparison.
    */

    static final int MAX = 100000; // a hundred thousand

    static int[] theArray = new int[MAX];

    public static void main(String[] args) {

        // to time sort algorithm
        NanoTimer timer0 = new NanoTimer();
        NanoTimer timer1 = new NanoTimer();
        NanoTimer timer2 = new NanoTimer();
        NanoTimer timer3 = new NanoTimer();

        // initialise array
        for (int i=0; i<MAX; i++) {
            theArray[i] = i;
        } // end for

        System.out.println("\nShuffling array...");
        timer0.setStartTime();
        randomiseArray();
        timer0.setStopTime();

        System.out.println("Applying quicksort algorithm...");
        timer1.setStartTime();
        quickSort();
        timer1.setStopTime();

        timer2.setStartTime();
        display();
        timer2.setStopTime();

        System.out.println("\nShuffling array...");
        randomiseArray();
        System.out.println("Applying bubblesort algorithm...");
        timer3.setStartTime();
        bubbleSort();
        timer3.setStopTime();

        //display();

        System.out.println("Size of array: "+MAX);
        System.out.println("Time to shuffle: "+timer0.toString());
        System.out.println("Time to quicksort: "+timer1.toString());
        System.out.println("Time to bubblesort: "+timer3.toString());
        System.out.println("Time to display result: "+timer2.toString());
    } // end main()

    public static void display() {
        System.out.println( Arrays.toString( theArray));
    } // display

    public static void randomiseArray() {
        Random r = new Random();
        int ran0, ran1, temp;

        for (int i=0; i<MAX; i++) {
            // choose random number
            ran0 = r.nextInt(MAX);

            // ensure ran0 and ran1 different
            do {
                // choose random number
                ran1 = r.nextInt(MAX);
            } while (ran1 == ran0);

            // swap positions in array
            temp = theArray[ran0];
            theArray[ran0] = theArray[ran1];
            theArray[ran1] = temp;
        } // end for
    } // end randomiseArray()

    public static int partition(int[] arr, int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];
        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) { // swap array elements
                tmp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = tmp;
                    } // end if
            }; // end while
        return i;
    } // end partition()

    public static void quickSort(int[] arr, int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    } // end quickSort(int[], int, int)

    public static void quickSort() {
        // this method provided for convenience
        quickSort(theArray, 0, MAX-1);
    } // end quickSort(int[]);

    public static void bubbleSort() {
        // apply bubblesort algorithm to array theArray
        int i,j,temp;
        int len = theArray.length;
        boolean swaps; // optimise code: when no swaps, array is sorted

        for (i=0; i<len-1; i++) {
            swaps = false;
            for (j=0; j<len-1-i; j++) {
                if (theArray[j]>theArray[j+1]) {
                    // swap
                    temp=theArray[j];
                    theArray[j]=theArray[j+1];
                    theArray[j+1]=temp;
                    swaps = true;
                }//end if
            } //end for j
            if (!swaps) break; // from outer loop
        } //end for i
    } //end bubbleSort()

} // end class TestQuicksort

class NanoTimer {

    /**
    *   Class:      NanoTimer.java
    *   Purpose:    Get program running times in nanoseconds (billionths of a second)
    *   Creator:    Chris Clarke
    *   Created:    03.04.2014
    */

    private long startTime = 0, runningTime = -1;

    public void setStartTime() {
        startTime = System.nanoTime();
    } // end setStartTime()

    public void setStopTime() {
        runningTime = System.nanoTime() - startTime;
    } // end setStopTime()

    public String toString() {
        if (runningTime == -1)
            return "Error in running time.";

        return runningTime+" nanoseconds";
    } // end toString()

} // end class NanoTimer