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 |
|
---|
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 |
|
---|
21 | * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
|
---|
22 | * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
|
---|
23 | * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
|
---|
24 | * POSSIBILITY OF SUCH DAMAGES.
|
---|
25 | *
|
---|
26 | * This software is not designed or intended for use in on-line control of
|
---|
27 | * aircraft, air traffic, aircraft navigation or aircraft communications; or in
|
---|
28 | * the design, construction, operation or maintenance of any nuclear
|
---|
29 |
|
---|
30 | * facility. Licensee represents and warrants that it will not use or
|
---|
31 | * redistribute the Software for such purposes.
|
---|
32 | */
|
---|
33 |
|
---|
34 | /**
|
---|
35 | * A quick sort demonstration algorithm
|
---|
36 | * SortAlgorithm.java
|
---|
37 | *
|
---|
38 | * @author James Gosling
|
---|
39 | * @author Kevin A. Smith
|
---|
40 | * @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
|
---|
41 | */
|
---|
42 |
|
---|
43 | package vishnu.testvis.sammon;
|
---|
44 |
|
---|
45 | import vishnu.testvis.object.*;
|
---|
46 |
|
---|
47 | public class QSortAlgorithmTableLength
|
---|
48 | {
|
---|
49 |
|
---|
50 | /**
|
---|
51 | * A version of pause() that makes it easier to ensure that we pause
|
---|
52 | * exactly the right number of times.
|
---|
53 |
|
---|
54 | */
|
---|
55 | private boolean pauseTrue(int lo, int hi) throws Exception {
|
---|
56 | return true;
|
---|
57 | }
|
---|
58 |
|
---|
59 | /** This is a generic version of C.A.R Hoare's Quick Sort
|
---|
60 | * algorithm. This will handle arrays that are already
|
---|
61 | * sorted, and arrays with duplicate keys.<BR>
|
---|
62 | *
|
---|
63 | * If you think of a one dimensional array as going from
|
---|
64 | * the lowest index on the left to the highest index on the right
|
---|
65 | * then the parameters to this function are lowest index or
|
---|
66 |
|
---|
67 | * left and highest index or right. The first time you call
|
---|
68 | * this function it will be with the parameters 0, a.length - 1.
|
---|
69 | *
|
---|
70 | * @param a an integer array
|
---|
71 | * @param lo0 left boundary of array partition
|
---|
72 | * @param hi0 right boundary of array partition
|
---|
73 | */
|
---|
74 | void QuickSort(LengthTable a[], int lo0, int hi0) throws Exception
|
---|
75 | {
|
---|
76 | int lo = lo0;
|
---|
77 | int hi = hi0;
|
---|
78 | int mid;
|
---|
79 |
|
---|
80 | if ( hi0 > lo0)
|
---|
81 | {
|
---|
82 |
|
---|
83 | /* Arbitrarily establishing partition element as the midpoint of
|
---|
84 |
|
---|
85 | * the array.
|
---|
86 | */
|
---|
87 | mid = a[ ( lo0 + hi0 ) / 2 ].length;
|
---|
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].length < mid ))
|
---|
96 | ++lo;
|
---|
97 |
|
---|
98 | /* find an element that is smaller than or equal to
|
---|
99 |
|
---|
100 | * the partition element starting from the right Index.
|
---|
101 | */
|
---|
102 | while( ( hi > lo0 ) && pauseTrue(lo0, hi0) && ( a[hi].length > mid ))
|
---|
103 | --hi;
|
---|
104 |
|
---|
105 | // if the indexes have not crossed, swap
|
---|
106 | if( lo <= hi )
|
---|
107 | {
|
---|
108 | swap(a, lo, hi);
|
---|
109 | ++lo;
|
---|
110 | --hi;
|
---|
111 | }
|
---|
112 | }
|
---|
113 |
|
---|
114 | /* If the right index has not reached the left side of array
|
---|
115 | * must now sort the left partition.
|
---|
116 |
|
---|
117 | */
|
---|
118 | if( lo0 < hi )
|
---|
119 | QuickSort( a, lo0, hi );
|
---|
120 |
|
---|
121 | /* If the left index has not reached the right side of array
|
---|
122 | * must now sort the right partition.
|
---|
123 | */
|
---|
124 | if( lo < hi0 )
|
---|
125 | QuickSort( a, lo, hi0 );
|
---|
126 |
|
---|
127 | }
|
---|
128 | }
|
---|
129 |
|
---|
130 | private void swap(LengthTable a[], int i, int j)
|
---|
131 | {
|
---|
132 | LengthTable T;
|
---|
133 | T = a[i];
|
---|
134 | a[i] = a[j];
|
---|
135 | a[j] = T;
|
---|
136 | }
|
---|
137 |
|
---|
138 | public void sort(LengthTable a[]) throws Exception
|
---|
139 | {
|
---|
140 | QuickSort(a, 0, a.length - 1);
|
---|
141 | }
|
---|
142 | }
|
---|