FileDocCategorySizeDatePackage
StrSort1.0.javaAPI DocExample4673Sat Nov 25 12:56:24 GMT 2000None

StrSort

public class StrSort extends Object
StrSort demonstrates sorting of strings using a quicksort. The actual sort is borrowed from the Java Demo Applet SortDemo, whose copyright allows its use.

Fields Summary
public static String[]
a
The list of strings to be sorted
Constructors Summary
Methods Summary
voidQuickSort(java.lang.String[] a, int lo0, int hi0)
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.
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

      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 );

      }
voiddump(java.lang.String[] a, java.lang.String title)


	     
		System.out.println("***** " + title + " *****");
		for (int i=0; i<a.length; i++)
			System.out.println("a["+i+"]="+a[i]);
public static voidmain(java.lang.String[] argv)
Simple main program to test the sorting

		System.out.println("StrSort Demo in Java");
		StrSort s = new StrSort();
		s.dump(a, "Before");
		s.QuickSort(a, 0, a.length-1);
		s.dump(a, "After");