View Javadoc

1   package org.wcb.common;
2   /***
3    * Copyright (C) 1999  Walter Bogaardt
4    *
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2 of the License, or (at your option) any later version.
9    *
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   *
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
18   *
19   *  Abstracts allows sort for tables and various objects 
20   */
21  
22  
23  /*** This is a version of C.A.R Hoare's Quick Sort
24   * algorithm.  This will handle arrays that are already
25   * sorted??, and arrays with duplicate keys.
26   *
27   * Requires that vector contain items that implement Comparable,
28   * or that a Comparator be provided.
29   */
30  public class ArraySorter {
31  
32  /* static Comparator asComparable = new Comparator() {
33  public boolean less(Object lhs, Object rhs)
34  { return ((Comparable) lhs).lessThan((Comparable) rhs); }
35  };
36  
37  // default assumes elements implement Comparable
38  static public void sort(Object[] array)
39  { sort(array, asComparable, 0, array.length-1); }
40  */
41      // use provided Comparator instead.
42      /***
43       * this allows the use of the quick sort algorithm
44       * @param array  The object array to sort
45       * @param cmp comparator object.
46       */
47      public static void sort(Object[] array, Comparator cmp)
48      {
49          sort(array, cmp, 0, array.length - 1);
50      }
51  
52      /***
53       * Takes the array and comparitor and starts sorting
54       * @param array the object arra
55       * @param cmp Comparator object
56       * @param left start postion of the left array
57       * @param right start postion of the right array
58       */
59      protected static void sort(Object[] array, Comparator cmp, int left, int right) {
60          int lo = left;
61          int hi = right;
62  
63          if (right > left)
64          {
65              Object mid = array[(left + right) / 2];
66              while (lo <= hi)
67              {
68                  while ((lo < right) && cmp.less(array[lo], mid))
69                  {
70                      ++lo;
71                  }
72                  while ((hi > left) && cmp.less(mid, array[hi]))
73                  {
74                      --hi;
75                  }
76                  if (lo <= hi)
77                  {
78                      swap(array, lo, hi);  ++lo;  --hi;
79                  }
80              }
81              if (left <  hi)
82              {
83                  sort(array, cmp, left,  hi);
84              }
85              if (lo < right)
86              {
87                  sort(array, cmp, lo, right);
88              }
89          }
90      }
91  
92      /***
93       * The array swapping routine
94       * @param array the array
95       * @param i the left element
96       * @param j the right element
97       */
98      private static void swap(Object[] array, int i, int j) {
99          Object obj = array[i];                    // t = a[i];
100         array[i] = array[j];                    // a[i] = a[j];
101         array[j] = obj;                           // a[j] = t;
102     }
103 }
104 
105 
106