KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > alfresco > web > data > QuickSort


1 /*
2  * Copyright (C) 2005 Alfresco, Inc.
3  *
4  * Licensed under the Mozilla Public License version 1.1
5  * with a permitted attribution clause. You may obtain a
6  * copy of the License at
7  *
8  * http://www.alfresco.org/legal/license.txt
9  *
10  * Unless required by applicable law or agreed to in writing,
11  * software distributed under the License is distributed on an
12  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
13  * either express or implied. See the License for the specific
14  * language governing permissions and limitations under the
15  * License.
16  */
17 package org.alfresco.web.data;
18
19 import java.util.List JavaDoc;
20
21 /**
22  * QuickSort
23  *
24  * Implementation of a locale sensitive Quick Sort algorithm. The sorting supports
25  * locale specific case sensitive, case in-sensitive and numeric data sorting. The
26  * numeric sorting handles integer, floating point and scientific formats, with
27  * short-circuit value parsing.
28  *
29  * @author Kevin Roast
30  */
31 public final class QuickSort extends Sort
32 {
33    /**
34     * Constructor
35     *
36     * @param data a the List of String[] data to sort
37     * @param column the column getter method to use on the row to sort
38     * @param bForward true for a forward sort, false for a reverse sort
39     * @param mode sort mode to use (see IDataContainer constants)
40     */
41    public QuickSort(List JavaDoc data, String JavaDoc column, boolean bForward, String JavaDoc mode)
42    {
43       super(data, column, bForward, mode);
44    }
45    
46    
47    // ------------------------------------------------------------------------------
48 // Sort Implementation
49
50    /**
51     * Runs the Quick Sort routine on the current dataset
52     */
53    public void sort()
54    {
55       if (this.data.size() != 0)
56       {
57          qsort(this.data, 0, this.data.size() - 1);
58       }
59    }
60    
61    
62    // ------------------------------------------------------------------------------
63 // Private methods
64
65    /**
66     * recursive Quicksort function.
67     *
68     * @param v the array out of which to take a slice.
69     * @param lower the lower bound of this slice.
70     * @param upper the upper bound of this slice.
71     */
72    private void qsort(final List JavaDoc v, final int lower, final int upper)
73    {
74       int sliceLength = upper - lower + 1 ;
75       if (sliceLength > 1)
76       {
77          if (sliceLength < 7)
78          {
79             // Insertion sort on smallest datasets
80 for (int i=lower; i<=upper; i++)
81             {
82                if (this.bForward == true)
83                {
84                   for (int j=i; j > lower && getComparator().compare(this.keys.get(j - 1), this.keys.get(j)) > 0; j--)
85                   {
86                      // swap both the keys and the actual row data
87 swap(this.keys, j - 1, j);
88                      swap(v, j - 1, j);
89                   }
90                }
91                else
92                {
93                   for (int j=i; j > lower && getComparator().compare(this.keys.get(j - 1), this.keys.get(j)) < 0; j--)
94                   {
95                      // swap both the keys and the actual row data
96 swap(this.keys, j - 1, j);
97                      swap(v, j - 1, j);
98                   }
99                }
100             }
101          }
102          else
103          {
104             int pivotIndex = partition(v, lower, upper);
105             qsort(v, lower, pivotIndex);
106             qsort(v, pivotIndex + 1, upper);
107          }
108       }
109    }
110    
111    /**
112     * Partition an array in two using the pivot value that is at the
113     * centre of the array being partitioned.
114     *
115     * This partition implementation based on that in Winder, R
116     * (1993) "Developing C++ Software", Wiley, p.395. NB. This
117     * implementation (unlike most others) does not guarantee that
118     * the split point contains the pivot value. Unlike other
119     * implementations, it requires only < (or >) relation and not
120     * both < and <= (or > and >=). Also, it seems easier to program
121     * and to understand.
122     *
123     * @param v the List out of which to take a slice.
124     * @param lower the lower bound of this slice.
125     * @param upper the upper bound of this slice.
126     */
127    private int partition(final List JavaDoc v, int lower, int upper)
128    {
129       List JavaDoc keys = this.keys;
130       Object JavaDoc pivotValue = keys.get((upper + lower + 1) >> 1) ;
131       
132       int size = keys.size();
133       
134       while (lower <= upper)
135       {
136          if (this.bForward == true)
137          {
138             while (getComparator().compare(keys.get(lower), pivotValue) < 0)
139             {
140                lower++;
141             }
142             while (getComparator().compare(pivotValue, keys.get(upper)) < 0)
143             {
144                upper--;
145             }
146          }
147          else
148          {
149             while (getComparator().compare(keys.get(lower), pivotValue) > 0)
150             {
151                lower++;
152             }
153             while (getComparator().compare(pivotValue, keys.get(upper)) > 0)
154             {
155                upper--;
156             }
157          }
158          if (lower <= upper)
159          {
160             if (lower < upper)
161             {
162                swap(keys, lower, upper);
163                swap(v, lower, upper);
164             }
165             lower++;
166             upper--;
167          }
168       }
169       
170       return upper;
171    }
172    
173 } // end class QuickSort
174
Popular Tags