KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sf > saxon > sort > QuickSort


1 package net.sf.saxon.sort;
2
3 /**
4  * This is a generic version of C.A.R Hoare's Quick Sort
5  * algorithm. This will handle arrays that are already
6  * sorted, and arrays with duplicate keys.<p>
7  *
8  * @author Patrick C. Beard (beard@netscape.com)
9  * Java Runtime Enthusiast -- "Will invoke interfaces for food."
10  *
11  * This code reached me (Michael Kay) via meteko.com; I'm assuming that it's OK
12  * to use because they copied it freely to me.
13  *
14  * Modified by MHK in May 2001 to sort any object that implements the Sortable
15  * interface, not only an array.
16  *
17  */
18  
19 public abstract class QuickSort {
20
21    /** This is a generic version of C.A.R Hoare's Quick Sort
22     * algorithm. This will handle arrays that are already
23     * sorted, and arrays with duplicate keys. <br>
24     *
25     * If you think of a one dimensional array as going from
26     * the lowest index on the left to the highest index on the right
27     * then the parameters to this function are lowest index or
28     * left and highest index or right. The first time you call
29     * this function it will be with the parameters 0, a.length - 1.
30     *
31     * @param a a Sortable object
32     * @param lo0 index of first element (initially typically 0)
33     * @param hi0 index of last element (initially typically length-1)
34     */
35     
36     public static void sort(Sortable a, int lo0, int hi0) {
37         int lo = lo0;
38         int hi = hi0;
39
40         if ( hi0 > lo0) {
41             /* Arbitrarily establishing partition element as the midpoint of
42             * the array.
43             */
44             int mid = ( lo0 + hi0 ) / 2;
45
46             // loop through the array until indices cross
47 while ( lo <= hi ) {
48                 /* find the first element that is greater than or equal to
49                 * the partition element starting from the left Index.
50                 */
51                 while (( lo < hi0 ) && ( a.compare(lo, mid) < 0 ))
52                     ++lo;
53
54                 /* find an element that is smaller than or equal to
55                 * the partition element starting from the right Index.
56                 */
57                 while (( hi > lo0 ) && ( a.compare(hi, mid) > 0 ))
58                     --hi;
59
60                 // if the indexes have not crossed, swap
61 if ( lo <= hi ) {
62                     if (lo!=hi) {
63                         a.swap(lo, hi);
64                         // keep mid pointing to the middle key value,
65 // not the middle position
66 if (lo==mid) {
67                             mid=hi;
68                         } else if (hi==mid) {
69                             mid=lo;
70                         }
71                     }
72                     ++lo;
73                     --hi;
74                 }
75             }
76
77             /* If the right index has not reached the left side of array
78             * must now sort the left partition.
79             */
80             if ( lo0 < hi )
81                 sort( a, lo0, hi );
82
83             /* If the left index has not reached the right side of array
84             * must now sort the right partition.
85             */
86             if ( lo < hi0 )
87                 sort( a, lo, hi0 );
88         }
89     }
90
91 }
92
93
94
Popular Tags