KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > versant > core > util > Quicksort


1
2 /*
3  * Copyright (c) 1998 - 2005 Versant Corporation
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License v1.0
6  * which accompanies this distribution, and is available at
7  * http://www.eclipse.org/legal/epl-v10.html
8  *
9  * Contributors:
10  * Versant Corporation - initial API and implementation
11  */
12 package com.versant.core.util;
13
14 import java.util.Comparator JavaDoc;
15
16 /**
17  * Quicksort implementation for sorting arrays. Unlike the merge sort in
18  * java.utils.Collections this one does not create any objects. There are
19  * two implementations, one for arrays of Comparable's and another that
20  * uses a comparator.
21  */
22 public class Quicksort {
23
24     private Quicksort() {
25     }
26
27     /**
28      * Sort the first size entries in a.
29      */
30     public static void quicksort(Object JavaDoc[] a, int size) {
31         quicksort(a, 0, size - 1);
32     }
33
34     /**
35      * Sort the entries in a between left and right inclusive.
36      */
37     public static void quicksort(Object JavaDoc[] a, int left, int right) {
38         int size = right - left + 1;
39         switch (size) {
40             case 0:
41             case 1:
42                 break;
43             case 2:
44                 if (compare(a[left], a[right]) > 0) swap(a, left, right);
45                 break;
46             case 3:
47                 if (compare(a[left], a[right - 1]) > 0) swap(a, left, right - 1);
48                 if (compare(a[left], a[right]) > 0) swap(a, left, right);
49                 if (compare(a[left + 1], a[right]) > 0) swap(a, left + 1, right);
50                 break;
51             default:
52                 int median = median(a, left, right);
53                 int partition = partition(a, left, right, median);
54                 quicksort(a, left, partition - 1);
55                 quicksort(a, partition + 1, right);
56         }
57     }
58
59     private static int compare(Object JavaDoc a, Object JavaDoc b) {
60         if (a == null) {
61             return b == null ? 0 : -1;
62         } else if (b == null) {
63             return +1;
64         } else {
65             return ((Comparable JavaDoc)a).compareTo(b);
66         }
67     }
68
69     private static void swap(Object JavaDoc[] a, int left, int right) {
70         Object JavaDoc t = a[left];
71         a[left] = a[right];
72         a[right] = t;
73     }
74
75     private static int median(Object JavaDoc[] a, int left, int right) {
76         int center = (left + right) / 2;
77         if (compare(a[left], a[center]) > 0) swap(a, left, center);
78         if (compare(a[left], a[right]) > 0) swap(a, left, right);
79         if (compare(a[center], a[right]) > 0) swap(a, center, right);
80         swap(a, center, right - 1);
81         return right - 1;
82     }
83
84     private static int partition(Object JavaDoc[] a, int left, int right, int pivotIndex) {
85         int leftIndex = left;
86         int rightIndex = right - 1;
87         while (true) {
88             while (compare(a[++leftIndex], a[pivotIndex]) < 0);
89             while (compare(a[--rightIndex], a[pivotIndex]) > 0);
90             if (leftIndex >= rightIndex) {
91                 break; // pointers cross so partition done
92 } else {
93                 swap(a, leftIndex, rightIndex);
94             }
95         }
96         swap(a, leftIndex, right - 1); // restore pivot
97 return leftIndex; // return pivot location
98 }
99
100     /**
101      * Sort the first size entries in a.
102      */
103     public static void quicksort(Object JavaDoc[] a, int size, Comparator JavaDoc c) {
104         quicksort(a, 0, size - 1, c);
105     }
106
107     /**
108      * Sort the entries in a between left and right inclusive.
109      */
110     public static void quicksort(Object JavaDoc[] a, int left, int right, Comparator JavaDoc c) {
111         int size = right - left + 1;
112         switch (size) {
113             case 0:
114             case 1:
115                 break;
116             case 2:
117                 if (c.compare(a[left], a[right]) > 0) swap(a, left, right);
118                 break;
119             case 3:
120                 if (c.compare(a[left], a[right - 1]) > 0) swap(a, left, right - 1);
121                 if (c.compare(a[left], a[right]) > 0) swap(a, left, right);
122                 if (c.compare(a[left + 1], a[right]) > 0) swap(a, left + 1, right);
123                 break;
124             default:
125                 int median = median(a, left, right, c);
126                 int partition = partition(a, left, right, median, c);
127                 quicksort(a, left, partition - 1, c);
128                 quicksort(a, partition + 1, right, c);
129         }
130     }
131
132     private static int median(Object JavaDoc[] a, int left, int right, Comparator JavaDoc c) {
133         int center = (left + right) / 2;
134         if (c.compare(a[left], a[center]) > 0) swap(a, left, center);
135         if (c.compare(a[left], a[right]) > 0) swap(a, left, right);
136         if (c.compare(a[center], a[right]) > 0) swap(a, center, right);
137         swap(a, center, right - 1);
138         return right - 1;
139     }
140
141     private static int partition(Object JavaDoc[] a, int left, int right,
142             int pivotIndex, Comparator JavaDoc c) {
143         int leftIndex = left;
144         int rightIndex = right - 1;
145         while (true) {
146             while (c.compare(a[++leftIndex], a[pivotIndex]) < 0);
147             while (c.compare(a[--rightIndex], a[pivotIndex]) > 0);
148             if (leftIndex >= rightIndex) {
149                 break; // pointers cross so partition done
150 } else {
151                 swap(a, leftIndex, rightIndex);
152             }
153         }
154         swap(a, leftIndex, right - 1); // restore pivot
155 return leftIndex; // return pivot location
156 }
157
158 }
159
Popular Tags