KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > turbine > util > QuickSort


1 package org.apache.turbine.util;
2
3 /*
4  * Copyright 2001-2004 The Apache Software Foundation.
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License")
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18
19 /**
20  * QuickSort - adapted from Doug Lea's Public Domain collection
21  * library.
22  *
23  * @author <a HREF="mailto:mbryson@mindspring.com">Dave Bryson</a>
24  * @version $Id: QuickSort.java,v 1.4.2.2 2004/05/20 03:16:38 seade Exp $
25  * @deprecated This class will be removed after the 2.3 release. It is
26  * not part of the Web Framework scope. If you need it, please
27  * use a sorting library for quicksort.
28  */
29 public class QuickSort
30 {
31     /**
32      * Sort array of Objects using the QuickSort algorithm.
33      *
34      * @param s An Object[].
35      * @param lo The current lower bound.
36      * @param hi The current upper bound.
37      * @param cmp A Comparable to compare two elements.
38      */
39     public static void quickSort(Object JavaDoc s[],
40                                  int lo,
41                                  int hi,
42                                  Comparable JavaDoc cmp)
43     {
44         if (lo >= hi)
45             return;
46
47         /*
48          * Use median-of-three(lo, mid, hi) to pick a partition. Also
49          * swap them into relative order while we are at it.
50          */
51         int mid = (lo + hi) / 2;
52
53         if (cmp.compare(s[lo], s[mid]) > 0)
54         {
55             // Swap.
56 Object JavaDoc tmp = s[lo];
57             s[lo] = s[mid];
58             s[mid] = tmp;
59         }
60
61         if (cmp.compare(s[mid], s[hi]) > 0)
62         {
63             // Swap .
64 Object JavaDoc tmp = s[mid];
65             s[mid] = s[hi];
66             s[hi] = tmp;
67
68             if (cmp.compare(s[lo], s[mid]) > 0)
69             {
70                 // Swap.
71 Object JavaDoc tmp2 = s[lo];
72                 s[lo] = s[mid];
73                 s[mid] = tmp2;
74             }
75         }
76
77         // Start one past lo since already handled lo.
78 int left = lo + 1;
79
80         // Similarly, end one before hi since already handled hi.
81 int right = hi - 1;
82
83         // If there are three or fewer elements, we are done.
84 if (left >= right)
85             return;
86
87         Object JavaDoc partition = s[mid];
88
89         for (; ;)
90         {
91             while (cmp.compare(s[right], partition) > 0)
92                 --right;
93
94             while (left < right &&
95                     cmp.compare(s[left], partition) <= 0)
96                 ++left;
97
98             if (left < right)
99             {
100                 // Swap.
101 Object JavaDoc tmp = s[left];
102                 s[left] = s[right];
103                 s[right] = tmp;
104
105                 --right;
106             }
107             else
108                 break;
109         }
110         quickSort(s, lo, left, cmp);
111         quickSort(s, left + 1, hi, cmp);
112     }
113
114     /**
115      * Sorts and array of objects.
116      *
117      * @param data An Object[].
118      * @param cmp A Comparable to compare two elements.
119      */
120     public void sort(Object JavaDoc[] data,
121                      Comparable JavaDoc cmp)
122     {
123         QuickSort.quickSort(data,
124                 0,
125                 data.length - 1,
126                 cmp);
127     }
128 }
129
Popular Tags