home *** CD-ROM | disk | FTP | other *** search
/ BUG 15 / BUGCD1998_06.ISO / aplic / jbuilder / jsamples.z / QSortAlgorithm.java < prev    next >
Text File  |  1997-07-30  |  5KB  |  133 lines
  1. // $Header: z:/admin/metro_examples/java/demo/SortDemo/rcs/QSortAlgorithm.java 1.1 1997/02/06 00:30:30 IPGIntel-2 Exp $ 
  2. /*
  3.  * @(#)QSortAlgorithm.java    1.6 96/12/06
  4.  *
  5.  * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
  6.  *
  7.  * Sun grants you ("Licensee") a non-exclusive, royalty free, license to use,
  8.  * modify and redistribute this software in source and binary code form,
  9.  * provided that i) this copyright notice and license appear on all copies of
  10.  * the software; and ii) Licensee does not utilize the software in a manner
  11.  * which is disparaging to Sun.
  12.  *
  13.  * This software is provided "AS IS," without a warranty of any kind. ALL
  14.  * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
  15.  * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
  16.  * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE
  17.  * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
  18.  * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS
  19.  * LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
  20.  * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
  21.  * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
  22.  * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
  23.  * POSSIBILITY OF SUCH DAMAGES.
  24.  *
  25.  * This software is not designed or intended for use in on-line control of
  26.  * aircraft, air traffic, aircraft navigation or aircraft communications; or in
  27.  * the design, construction, operation or maintenance of any nuclear
  28.  * facility. Licensee represents and warrants that it will not use or
  29.  * redistribute the Software for such purposes.
  30.  */
  31.  
  32. /**
  33.  * A quick sort demonstration algorithm
  34.  * SortAlgorithm.java
  35.  *
  36.  * @author James Gosling
  37.  * @author Kevin A. Smith
  38.  * @version     @(#)QSortAlgorithm.java    1.3, 29 Feb 1996
  39.  */
  40. public class QSortAlgorithm extends SortAlgorithm 
  41. {
  42.  
  43.     /**
  44.      * A version of pause() that makes it easier to ensure that we pause
  45.      * exactly the right number of times.
  46.      */
  47.     private boolean pauseTrue(int lo, int hi) throws Exception {
  48.     super.pause(lo, hi);
  49.     return true;
  50.     }
  51.  
  52.    /** This is a generic version of C.A.R Hoare's Quick Sort 
  53.     * algorithm.  This will handle arrays that are already
  54.     * sorted, and arrays with duplicate keys.<BR>
  55.     *
  56.     * If you think of a one dimensional array as going from
  57.     * the lowest index on the left to the highest index on the right
  58.     * then the parameters to this function are lowest index or
  59.     * left and highest index or right.  The first time you call
  60.     * this function it will be with the parameters 0, a.length - 1.
  61.     *
  62.     * @param a       an integer array
  63.     * @param lo0     left boundary of array partition
  64.     * @param hi0     right boundary of array partition
  65.     */
  66.    void QuickSort(int a[], int lo0, int hi0) throws Exception
  67.    {
  68.       int lo = lo0;
  69.       int hi = hi0;
  70.       int mid;
  71.  
  72.       if ( hi0 > lo0)
  73.       {
  74.  
  75.          /* Arbitrarily establishing partition element as the midpoint of
  76.           * the array.
  77.           */
  78.          mid = a[ ( lo0 + hi0 ) / 2 ];
  79.  
  80.          // loop through the array until indices cross
  81.          while( lo <= hi )
  82.          {
  83.             /* find the first element that is greater than or equal to 
  84.              * the partition element starting from the left Index.
  85.              */
  86.          while( ( lo < hi0 ) && pauseTrue(lo0, hi0) && ( a[lo] < mid ))
  87.          ++lo;
  88.  
  89.             /* find an element that is smaller than or equal to 
  90.              * the partition element starting from the right Index.
  91.              */
  92.          while( ( hi > lo0 ) && pauseTrue(lo0, hi0) && ( a[hi] > mid ))
  93.          --hi;
  94.  
  95.             // if the indexes have not crossed, swap
  96.             if( lo <= hi ) 
  97.             {
  98.                swap(a, lo, hi);
  99.                ++lo;
  100.                --hi;
  101.             }
  102.          }
  103.  
  104.          /* If the right index has not reached the left side of array
  105.           * must now sort the left partition.
  106.           */
  107.          if( lo0 < hi )
  108.             QuickSort( a, lo0, hi );
  109.  
  110.          /* If the left index has not reached the right side of array
  111.           * must now sort the right partition.
  112.           */
  113.          if( lo < hi0 )
  114.             QuickSort( a, lo, hi0 );
  115.  
  116.       }
  117.    }
  118.  
  119.    private void swap(int a[], int i, int j)
  120.    {
  121.       int T;
  122.       T = a[i]; 
  123.       a[i] = a[j];
  124.       a[j] = T;
  125.  
  126.    }
  127.  
  128.    public void sort(int a[]) throws Exception
  129.    {
  130.       QuickSort(a, 0, a.length - 1);
  131.    }
  132. }
  133.