01: /*
02: * @(#)Sort.java 1.15 06/10/10
03: *
04: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
05: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
06: *
07: * This program is free software; you can redistribute it and/or
08: * modify it under the terms of the GNU General Public License version
09: * 2 only, as published by the Free Software Foundation.
10: *
11: * This program is distributed in the hope that it will be useful, but
12: * WITHOUT ANY WARRANTY; without even the implied warranty of
13: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: * General Public License version 2 for more details (a copy is
15: * included at /legal/license.txt).
16: *
17: * You should have received a copy of the GNU General Public License
18: * version 2 along with this work; if not, write to the Free Software
19: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20: * 02110-1301 USA
21: *
22: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
23: * Clara, CA 95054 or visit www.sun.com if you need additional
24: * information or have any questions.
25: *
26: */
27:
28: /**
29: * Sort: a class that uses the quicksort algorithm to sort an
30: * array of objects.
31: *
32: * @version 1.9, 02/02/00
33: * @author Sunita Mani
34: */package sun.misc;
35:
36: public class Sort {
37:
38: private static void swap(Object arr[], int i, int j) {
39: Object tmp;
40:
41: tmp = arr[i];
42: arr[i] = arr[j];
43: arr[j] = tmp;
44: }
45:
46: /**
47: * quicksort the array of objects.
48: *
49: * @param arr[] - an array of objects
50: * @param left - the start index - from where to begin sorting
51: * @param right - the last index.
52: * @param comp - an object that implemnts the Compare interface to resolve thecomparison.
53: */
54: public static void quicksort(Object arr[], int left, int right,
55: Compare comp) {
56: int i, last;
57:
58: if (left >= right) { /* do nothing if array contains fewer than two */
59: return; /* two elements */
60: }
61: swap(arr, left, (left + right) / 2);
62: last = left;
63: for (i = left + 1; i <= right; i++) {
64: if (comp.doCompare(arr[i], arr[left]) < 0) {
65: swap(arr, ++last, i);
66: }
67: }
68: swap(arr, left, last);
69: quicksort(arr, left, last - 1, comp);
70: quicksort(arr, last + 1, right, comp);
71: }
72:
73: public static void quicksort(Object arr[], Compare comp) {
74: quicksort(arr, 0, arr.length - 1, comp);
75: }
76: }
|