/* The contents 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
*/
public class StringSort {
/** 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
*/
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 );
}
}
}
|