A Quick Sort Demonstration Algorithm SortAlgorithm.java

package com.sun.example;
 
/*
 * The remainder of this file is borrowed from: @(#)QSortAlgorithm.java 1.3 29 Feb 1996 James
 * Gosling
 * 
 * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
 * 
 * Permission to use, copy, modify, and distribute this software and its documentation for
 * NON-COMMERCIAL or COMMERCIAL purposes and without fee is hereby granted. Please refer to the file
 * http://www.javasoft.com/copy_trademarks.html for further important copyright and trademark
 * information and to http://www.javasoft.com/licensing.html for further important licensing
 * information for the Java (tm) Technology.
 * 
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
 * LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 * 
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE CONTROL EQUIPMENT IN
 * HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR
 * FACILITIES, AIRCRAFT NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE SOFTWARE COULD LEAD DIRECTLY TO
 * DEATH, PERSONAL INJURY, OR SEVERE PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR HIGH RISK ACTIVITIES.
 */
 
/**
 * A quick sort demonstration algorithm SortAlgorithm.java
 * 
 * @author James Gosling
 * @author Kevin A. Smith
 * @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
 */
 
/**
 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This will handle arrays that are
 * already sorted, and arrays with duplicate keys. <BR>
 * 
 * If you think of a one dimensional array as going from the lowest index on the left to the highest
 * index on the right then the parameters to this function are lowest index or left and highest
 * index or right. The first time you call this function it will be with the parameters 0, a.length
 * - 1.
 * 
 * @param a
 *            a string array
 * @param lo0
 *            left boundary of array partition
 * @param hi0
 *            right boundary of array partition
 */
public class Sort {
    void QuickSort(String a[], int lo0, int hi0) {
	int lo = lo0;
	int hi = hi0;
	String mid;
 
	if (hi0 > lo0) {
 
	    /*
	     * Arbitrarily establishing partition element as the midpoint of the array.
	     */
	    mid = a[(lo0 + hi0) / 2];
 
	    // loop through the array until indices cross
	    while (lo <= hi) {
		/*
		 * find the first element that is greater than or equal to the partition element
		 * starting from the left Index.
		 */
		while ((lo < hi0) && (a[lo].compareTo(mid) < 0))
		    ++lo;
 
		/*
		 * find an element that is smaller than or equal to the partition element starting
		 * from the right Index.
		 */
		while ((hi > lo0) && (a[hi].compareTo(mid) > 0))
		    --hi;
 
		// if the indexes have not crossed, swap
		if (lo <= hi) {
		    String t = a[hi];
		    a[hi] = a[lo];
		    a[lo] = t;
 
		    ++lo;
		    --hi;
		}
	    }
 
	    /*
	     * If the right index has not reached the left side of array must now sort the left
	     * partition.
	     */
	    if (lo0 < hi)
		QuickSort(a, lo0, hi);
 
	    /*
	     * If the left index has not reached the right side of array must now sort the right
	     * partition.
	     */
	    if (lo < hi0)
		QuickSort(a, lo, hi0);
 
	}
    }
}