Nightly Builds

This is an easy verion of the popular quick sort algorithm implemented in Java.  Since the main aim is to keep it simple, this does not use the in-place partitioning algorithm.

package quicksort;

/**
 *
 * @author a435104
 */
public class Main {

	static int callCount = 0;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        int[] array1 = {9,11,2,5,3,1,12};

        quicksort("main", array1);

        System.out.print("Sorted Array : ");
        printArray(array1);
    }

    /**
     * From - http://en.wikipedia.org/wiki/Quicksort
     *
     * Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
     * The steps are:
     *
   	 * 1. Pick an element, called a pivot, from the list.
     * 2. Reorder the list so that all elements which are less than the pivot come before the
     *    pivot and so that all elements greater than the pivot come after it (equal values can go either way).
     *    After this partitioning, the pivot is in its final position. This is called the partition operation.
     * 3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
     *
     *
     */
    public static int[] quicksort(String debugString, int array[]) {

    	callCount++;

    	System.out.println("\nQuickSort -> callCount :" + callCount + " arrayName :" + debugString);
    	System.out.print("Array Elements    -> ");
    	printArray(array);

    	//base case
        if (array == null || array.length  " + pivot);

        // Create two arrays, one to hold the elements lesser than pivot
        // another to hold elements greater than pivot.
        int[] lesserArray = new int[array.length];
        int[] greaterArray = new int[array.length];

        int gndx = 0;
        int lndx = 0;

        // Next two for loops performs the partition operation.
        // Rearranges elements around pivot such that,
        // elements greater than or equal to pivot goes to greaterArray and
        // elements less than pivot goes to lesserArray.

        for (int ndx = 0; ndx = array[pivotNdx]) {
                greaterArray[gndx] = array[ndx];
                gndx++;
            }
            else {
                lesserArray[lndx] = array[ndx];
                lndx++;
            }
        }

        for (int ndx = pivotNdx + 1; ndx = array[pivotNdx]) {
                greaterArray[gndx] = array[ndx];
                gndx++;
            }
            else {
                lesserArray[lndx] = array[ndx];
                lndx++;
            }
        }
        // end of partitioning.

        // trim lesserArray
        int[] tempArray = new int[lndx];
        System.arraycopy(lesserArray, 0, tempArray, 0, lndx);
        lesserArray = tempArray;

        // trim greaterArray
        tempArray = new int[gndx];
        System.arraycopy(greaterArray, 0, tempArray, 0, gndx);
        greaterArray = tempArray;

        System.out.print("After partitioning, lesserArray -> ");
        printArray(lesserArray);

        System.out.print("After partitioning, greaterArray -> ");
        printArray(greaterArray);

        // recursively call quicksort on lesserArray and greaterArray.
        return concatenate(quicksort("lesserArray", lesserArray), pivot, quicksort("greaterArray", greaterArray), array);

    }

    private static int[] concatenate(int[] lesserArray, int pivot, int[] greaterArray, int[] array) {

        System.arraycopy(lesserArray, 0, array, 0, lesserArray.length);

        array[lesserArray.length] = pivot;

        System.arraycopy(greaterArray, 0, array, lesserArray.length + 1, greaterArray.length);

        return array;
    }

    private static void printArray(int array[]) {
        for (int i=0;i<array.length;i++) {
            System.out.print(array[i] + ", ");
        }

        System.out.println("");
    }
}