|
1
16 package net.sf.cglib.util;
17
18 import java.util.*;
19
20 abstract class SorterTemplate {
21 private static final int MERGESORT_THRESHOLD = 12;
22 private static final int QUICKSORT_THRESHOLD = 7;
23
24 abstract protected void swap(int i, int j);
25 abstract protected int compare(int i, int j);
26
27 protected void quickSort(int lo, int hi) {
28 quickSortHelper(lo, hi);
29 insertionSort(lo, hi);
30 }
31
32 private void quickSortHelper(int lo, int hi) {
33 for (;;) {
34 int diff = hi - lo;
35 if (diff <= QUICKSORT_THRESHOLD) {
36 break;
37 }
38 int i = (hi + lo) / 2;
39 if (compare(lo, i) > 0) {
40 swap(lo, i);
41 }
42 if (compare(lo, hi) > 0) {
43 swap(lo, hi);
44 }
45 if (compare(i, hi) > 0) {
46 swap(i, hi);
47 }
48 int j = hi - 1;
49 swap(i, j);
50 i = lo;
51 int v = j;
52 for (;;) {
53 while (compare(++i, v) < 0) {
54 ;
55 }
56 while (compare(--j, v) > 0) {
57 ;
58 }
59 if (j < i) {
60 break;
61 }
62 swap(i, j);
63 }
64 swap(i, hi - 1);
65 if (j - lo <= hi - i + 1) {
66 quickSortHelper(lo, j);
67 lo = i + 1;
68 } else {
69 quickSortHelper(i + 1, hi);
70 hi = j;
71 }
72 }
73 }
74
75 private void insertionSort(int lo, int hi) {
76 for (int i = lo + 1 ; i <= hi; i++) {
77 for (int j = i; j > lo; j--) {
78 if (compare(j - 1, j) > 0) {
79 swap(j - 1, j);
80 } else {
81 break;
82 }
83 }
84 }
85 }
86
87 protected void mergeSort(int lo, int hi) {
88 int diff = hi - lo;
89 if (diff <= MERGESORT_THRESHOLD) {
90 insertionSort(lo, hi);
91 return;
92 }
93 int mid = lo + diff / 2;
94 mergeSort(lo, mid);
95 mergeSort(mid, hi);
96 merge(lo, mid, hi, mid - lo, hi - mid);
97 }
98
99 private void merge(int lo, int pivot, int hi, int len1, int len2) {
100 if (len1 == 0 || len2 == 0) {
101 return;
102 }
103 if (len1 + len2 == 2) {
104 if (compare(pivot, lo) < 0) {
105 swap(pivot, lo);
106 }
107 return;
108 }
109 int first_cut, second_cut;
110 int len11, len22;
111 if (len1 > len2) {
112 len11 = len1 / 2;
113 first_cut = lo + len11;
114 second_cut = lower(pivot, hi, first_cut);
115 len22 = second_cut - pivot;
116 } else {
117 len22 = len2 / 2;
118 second_cut = pivot + len22;
119 first_cut = upper(lo, pivot, second_cut);
120 len11 = first_cut - lo;
121 }
122 rotate(first_cut, pivot, second_cut);
123 int new_mid = first_cut + len22;
124 merge(lo, first_cut, new_mid, len11, len22);
125 merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
126 }
127
128 private void rotate(int lo, int mid, int hi) {
129 int lot = lo;
130 int hit = mid - 1;
131 while (lot < hit) {
132 swap(lot++, hit--);
133 }
134 lot = mid; hit = hi - 1;
135 while (lot < hit) {
136 swap(lot++, hit--);
137 }
138 lot = lo; hit = hi - 1;
139 while (lot < hit) {
140 swap(lot++, hit--);
141 }
142 }
143
144 private int lower(int lo, int hi, int val) {
145 int len = hi - lo;
146 while (len > 0) {
147 int half = len / 2;
148 int mid= lo + half;
149 if (compare(mid, val) < 0) {
150 lo = mid + 1;
151 len = len - half -1;
152 } else {
153 len = half;
154 }
155 }
156 return lo;
157 }
158
159 private int upper(int lo, int hi, int val) {
160 int len = hi - lo;
161 while (len > 0) {
162 int half = len / 2;
163 int mid = lo + half;
164 if (compare(val, mid) < 0) {
165 len = half;
166 } else {
167 lo = mid + 1;
168 len = len - half -1;
169 }
170 }
171 return lo;
172 }
173 }
174 |
Popular Tags |
Java API By Example, From Geeks To Geeks.