01: /* ===========================================================================
02: * $RCSfile: Sort.java,v $
03: * ===========================================================================
04: *
05: * RetroGuard -- an obfuscation package for Java classfiles.
06: *
07: * Copyright (c) 1998-2006 Mark Welsh (markw@retrologic.com)
08: *
09: * This program can be redistributed and/or modified under the terms of the
10: * Version 2 of the GNU General Public License as published by the Free
11: * Software Foundation.
12: *
13: * This program is distributed in the hope that it will be useful,
14: * but WITHOUT ANY WARRANTY; without even the implied warranty of
15: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16: * GNU General Public License for more details.
17: *
18: */
19:
20: package COM.rl.util;
21:
22: import java.io.*;
23: import java.util.*;
24:
25: /**
26: * Various sorting algorithms. The comparison interface is Compare.
27: *
28: * @see Compare
29: *
30: * @author Mark Welsh
31: */
32: public class Sort {
33: // Constants -------------------------------------------------------------
34:
35: // Fields ----------------------------------------------------------------
36:
37: // Class Methods ---------------------------------------------------------
38: /** Quicksort. */
39: public static void quicksort(Object[] data, Compare cmp) {
40: if (data != null && data.length > 1 && cmp != null) {
41: quicksort(data, 0, data.length - 1, cmp);
42: }
43: }
44:
45: private static void quicksort(Object[] data, int left, int right,
46: Compare cmp) {
47: int i = left;
48: int j = right;
49:
50: // Sort range of data [left, right] into less, equal, more groups
51: Object mid = data[(left + right) / 2];
52: do {
53: while (cmp.isLess(data[i], mid))
54: i++;
55: while (cmp.isLess(mid, data[j]))
56: j--;
57: if (i <= j) {
58: Object tmp = data[i];
59: data[i] = data[j];
60: data[j] = tmp;
61: i++;
62: j--;
63: }
64: } while (i <= j);
65:
66: // Sort less group, if necessary
67: if (left < j) {
68: quicksort(data, left, j, cmp);
69: }
70:
71: // Sort more group, if necessary
72: if (i < right) {
73: quicksort(data, i, right, cmp);
74: }
75: }
76:
77: // Instance Methods ------------------------------------------------------
78:
79: }
|