RevisedQuicksort.java

/*
    RevisedQuicksort.java
    CIS 260
    David Klick
    2/8/06

Revision of Quicksort algorithm demonstration
    designed to make it easier to modify.
*/

import java.text.*;
import java.util.Random;

public class RevisedQuicksort {
    public static void main(String[] args) {
        long startTime, elapsedTime;
        int array_size = 50000;
        Random rnd = new Random();

if (args.length > 0) {
           try {
              array_size = Integer.parseInt(args[0]);
              if (array_size < 10) array_size = 10;
           } catch (Exception e) {
              // ignore errors
           }
        }
        System.out.println("Sorting an array of " + array_size + " doubles");
        double[] work = new double[array_size];
        double[] hold = new double[array_size];

// create an array of random doubles
        for (int i=0; i<hold.length; i++) {
            hold[i] = rnd.nextDouble();
        }

// copy holding array to working array and do quick sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using quick sort ");
        startTime = System.currentTimeMillis();
        quicksort(work, 0, work.length-1);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- quick sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");
    }

public static void copyArray(double[] from, double[] to) {
        int max = from.length;
        if (max != to.length) {
            System.out.println("*** Warning: copyArray called with different length arrays ***");
            max = to.length;
        }
        for (int i=0; i<max; i++) to[i] = from[i];
    }

public static boolean isSorted(double[] a) {
        for (int i=0; i<a.length-1; i++) {
            if (a[i] > a[i+1]) return false;
        }
        return true;
    }

public static void quicksort(double[] a, int left, int right) {
        int pivotNdx, l_hold = left, r_hold = right;
        double pivot = a[left];

while (left < right) {
            while ((a[right] >= pivot) && (left < right)) right--;
            if (left != right) a[left++] = a[right];
            while ((a[left] <= pivot) && (left < right)) left++;
            if (left != right) a[right--] = a[left];
        }
        a[left] = pivot;
        pivotNdx = left;
        left = l_hold;
        right = r_hold;
        if (left < pivotNdx) quicksort(a, left, pivotNdx-1);
        if (right > pivotNdx) quicksort(a, pivotNdx+1, right);
    }

}

/*
    Sample output:

Sorting an array of 50000 doubles
    Sorting work array using quick sort - elapsed time: 16ms
*/