01: package net.sf.saxon.sort;
02:
03: /**
04: * This is a generic version of C.A.R Hoare's Quick Sort
05: * algorithm. This will handle arrays that are already
06: * sorted, and arrays with duplicate keys.<p>
07: *
08: * @author Patrick C. Beard (beard@netscape.com)
09: * 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: }
|