home *** CD-ROM | disk | FTP | other *** search
/ Java 1996 August / Java - Summer 1996.iso / windows / java / demo / sortdemo / qsortalgorithm.java < prev    next >
Encoding:
Java Source  |  1996-04-29  |  4.1 KB  |  128 lines
  1. /*
  2.  * @(#)QSortAlgorithm.java    1.3   29 Feb 1996 James Gosling
  3.  *
  4.  * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software
  7.  * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
  8.  * without fee is hereby granted. 
  9.  * Please refer to the file http://www.javasoft.com/copy_trademarks.html
  10.  * for further important copyright and trademark information and to
  11.  * http://www.javasoft.com/licensing.html for further important
  12.  * licensing information for the Java (tm) Technology.
  13.  * 
  14.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  15.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  16.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  17.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  18.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  19.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  20.  * 
  21.  * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
  22.  * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
  23.  * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
  24.  * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
  25.  * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
  26.  * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
  27.  * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
  28.  * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
  29.  * HIGH RISK ACTIVITIES.
  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.    /** This is a generic version of C.A.R Hoare's Quick Sort 
  43.     * algorithm.  This will handle arrays that are already
  44.     * sorted, and arrays with duplicate keys.<BR>
  45.     *
  46.     * If you think of a one dimensional array as going from
  47.     * the lowest index on the left to the highest index on the right
  48.     * then the parameters to this function are lowest index or
  49.     * left and highest index or right.  The first time you call
  50.     * this function it will be with the parameters 0, a.length - 1.
  51.     *
  52.     * @param a       an integer array
  53.     * @param lo0     left boundary of array partition
  54.     * @param hi0     right boundary of array partition
  55.     */
  56.    void QuickSort(int a[], int lo0, int hi0) throws Exception
  57.    {
  58.       int lo = lo0;
  59.       int hi = hi0;
  60.       int mid;
  61.  
  62.       // pause for redraw
  63.       pause(lo, hi);
  64.       if ( hi0 > lo0)
  65.       {
  66.  
  67.          /* Arbitrarily establishing partition element as the midpoint of
  68.           * the array.
  69.           */
  70.          mid = a[ ( lo0 + hi0 ) / 2 ];
  71.  
  72.          // loop through the array until indices cross
  73.          while( lo <= hi )
  74.          {
  75.             /* find the first element that is greater than or equal to 
  76.              * the partition element starting from the left Index.
  77.              */
  78.             while( ( lo < hi0 ) && ( a[lo] < mid ) )
  79.                ++lo;
  80.  
  81.             /* find an element that is smaller than or equal to 
  82.              * the partition element starting from the right Index.
  83.              */
  84.             while( ( hi > lo0 ) && ( a[hi] > mid ) )
  85.                --hi;
  86.  
  87.             // if the indexes have not crossed, swap
  88.             if( lo <= hi ) 
  89.             {
  90.                swap(a, lo, hi);
  91.                // pause
  92.                pause();
  93.  
  94.                ++lo;
  95.                --hi;
  96.             }
  97.          }
  98.  
  99.          /* If the right index has not reached the left side of array
  100.           * must now sort the left partition.
  101.           */
  102.          if( lo0 < hi )
  103.             QuickSort( a, lo0, hi );
  104.  
  105.          /* If the left index has not reached the right side of array
  106.           * must now sort the right partition.
  107.           */
  108.          if( lo < hi0 )
  109.             QuickSort( a, lo, hi0 );
  110.  
  111.       }
  112.    }
  113.  
  114.    private void swap(int a[], int i, int j)
  115.    {
  116.       int T;
  117.       T = a[i]; 
  118.       a[i] = a[j];
  119.       a[j] = T;
  120.  
  121.    }
  122.  
  123.    public void sort(int a[]) throws Exception
  124.    {
  125.       QuickSort(a, 0, a.length - 1);
  126.    }
  127. }
  128.