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