KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jodd > util > sort > FastQuickSort


1 // Copyright (c) 2003-2007, Jodd Team (jodd.sf.net). All Rights Reserved.
2
3 package jodd.util.sort;
4
5 import java.util.Comparator JavaDoc;
6
7 import jodd.util.ComparableComparator;
8
9 /**
10  * Maybe the fastes implementation of famouse Quick-Sort
11  * algorithm. It is even faster than Denisa Ahrensa implementation that
12  * performs 7.5s for sorting a milion objects, this implementation
13  * sorts for 6.8s. However, {@link FastMergeSort} is much faster.
14  */
15 public class FastQuickSort implements Sorter {
16     
17     public void qsort(Object JavaDoc[] c, Comparator JavaDoc comparator) {
18         int i, j, left = 0, right = c.length - 1, stack_pointer = -1;
19         int[] stack = new int[128];
20         Object JavaDoc swap, temp;
21         while (true) {
22             if (right - left <= 7) {
23                 for (j = left + 1; j <= right; j++) {
24                     swap = c[j];
25                     i = j - 1;
26                     while (i >= left && comparator.compare(c[i], swap) > 0) {
27                         c[i + 1] = c[i--];
28                     }
29                     c[i + 1] = swap;
30                 }
31                 if (stack_pointer == -1) {
32                     break;
33                 }
34                 right = stack[stack_pointer--];
35                 left = stack[stack_pointer--];
36             } else {
37                 int median = (left + right) >> 1;
38                 i = left + 1;
39                 j = right;
40                 swap = c[median]; c[median] = c[i]; c[i] = swap;
41                 if (comparator.compare(c[left], c[right]) > 0) {
42                     swap = c[left]; c[left] = c[right]; c[right] = swap;
43                 }
44                 if (comparator.compare(c[i], c[right]) > 0) {
45                     swap = c[i]; c[i] = c[right]; c[right] = swap;
46                 }
47                 if (comparator.compare(c[left], c[i]) > 0) {
48                     swap = c[left]; c[left] = c[i]; c[i] = swap;
49                 }
50                 temp = c[i];
51                 while (true) {
52                     while (comparator.compare(c[++i], temp) < 0);
53                     while (comparator.compare(c[--j], temp) > 0);
54                     if (j < i) {
55                         break;
56                     }
57                     swap = c[i]; c[i] = c[j]; c[j] = swap;
58                 }
59                 c[left + 1] = c[j];
60                 c[j] = temp;
61                 if (right - i + 1 >= j - left) {
62                     stack[++stack_pointer] = i;
63                     stack[++stack_pointer] = right;
64                     right = j - 1;
65                 } else {
66                     stack[++stack_pointer] = left;
67                     stack[++stack_pointer] = j - 1;
68                     left = i;
69                 }
70             }
71         }
72     }
73
74     public void sort(Object JavaDoc a[], Comparator JavaDoc comparator) {
75         qsort(a, comparator);
76     }
77     
78     public void sort(Comparable JavaDoc a[]) {
79         qsort(a, ComparableComparator.instance());
80     }
81 }
82
Popular Tags