KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > QSortAlgorithm


1 /*
2  * @(#)QSortAlgorithm.java 1.13 06/02/22
3  *
4  * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * -Redistribution of source code must retain the above copyright notice, this
10  * list of conditions and the following disclaimer.
11  *
12  * -Redistribution in binary form must reproduce the above copyright notice,
13  * this list of conditions and the following disclaimer in the documentation
14  * and/or other materials provided with the distribution.
15  *
16  * Neither the name of Sun Microsystems, Inc. or the names of contributors may
17  * be used to endorse or promote products derived from this software without
18  * specific prior written permission.
19  *
20  * This software is provided "AS IS," without a warranty of any kind. ALL
21  * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
22  * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
23  * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN")
24  * AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
25  * AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
26  * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
27  * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
28  * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
29  * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE,
30  * EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
31  *
32  * You acknowledge that this software is not designed, licensed or intended
33  * for use in the design, construction, operation or maintenance of any
34  * nuclear facility.
35  */
36
37 /*
38  * @(#)QSortAlgorithm.java 1.13 06/02/22
39  */
40
41 /**
42  * A quick sort demonstration algorithm
43  * SortAlgorithm.java
44  *
45  * @author James Gosling
46  * @author Kevin A. Smith
47  * @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
48  */
49 public class QSortAlgorithm extends SortAlgorithm
50 {
51
52     /**
53      * A version of pause() that makes it easier to ensure that we pause
54      * exactly the right number of times.
55      */
56     private boolean pauseTrue(int lo, int hi) throws Exception JavaDoc {
57     super.pause(lo, hi);
58     return true;
59     }
60
61    /** This is a generic version of C.A.R Hoare's Quick Sort
62     * algorithm. This will handle arrays that are already
63     * sorted, and arrays with duplicate keys.<BR>
64     *
65     * If you think of a one dimensional array as going from
66     * the lowest index on the left to the highest index on the right
67     * then the parameters to this function are lowest index or
68     * left and highest index or right. The first time you call
69     * this function it will be with the parameters 0, a.length - 1.
70     *
71     * @param a an integer array
72     * @param lo0 left boundary of array partition
73     * @param hi0 right boundary of array partition
74     */
75    void QuickSort(int a[], int lo0, int hi0) throws Exception JavaDoc
76    {
77       int lo = lo0;
78       int hi = hi0;
79       int mid;
80
81       if ( hi0 > lo0)
82       {
83
84          /* Arbitrarily establishing partition element as the midpoint of
85           * the array.
86           */
87          mid = a[ ( lo0 + hi0 ) / 2 ];
88
89          // loop through the array until indices cross
90 while( lo <= hi )
91          {
92             /* find the first element that is greater than or equal to
93              * the partition element starting from the left Index.
94              */
95          while( ( lo < hi0 ) && pauseTrue(lo0, hi0) && ( a[lo] < mid ))
96          ++lo;
97
98             /* find an element that is smaller than or equal to
99              * the partition element starting from the right Index.
100              */
101          while( ( hi > lo0 ) && pauseTrue(lo0, hi0) && ( a[hi] > mid ))
102          --hi;
103
104             // if the indexes have not crossed, swap
105 if( lo <= hi )
106             {
107                swap(a, lo, hi);
108                ++lo;
109                --hi;
110             }
111          }
112
113          /* If the right index has not reached the left side of array
114           * must now sort the left partition.
115           */
116          if( lo0 < hi )
117             QuickSort( a, lo0, hi );
118
119          /* If the left index has not reached the right side of array
120           * must now sort the right partition.
121           */
122          if( lo < hi0 )
123             QuickSort( a, lo, hi0 );
124
125       }
126    }
127
128    private void swap(int a[], int i, int j)
129    {
130       int T;
131       T = a[i];
132       a[i] = a[j];
133       a[j] = T;
134
135    }
136
137    public void sort(int a[]) throws Exception JavaDoc
138    {
139       QuickSort(a, 0, a.length - 1);
140    }
141 }
142
Popular Tags