|
1
54 package org.logicalcobwebs.cglib.util;
55
56 import java.util.*;
57
58 abstract class SorterTemplate {
59 private static final int MERGESORT_THRESHOLD = 12;
60 private static final int QUICKSORT_THRESHOLD = 7;
61
62 abstract protected void swap(int i, int j);
63 abstract protected int compare(int i, int j);
64
65 protected void quickSort(int lo, int hi) {
66 quickSortHelper(lo, hi);
67 insertionSort(lo, hi);
68 }
69
70 private void quickSortHelper(int lo, int hi) {
71 for (;;) {
72 int diff = hi - lo;
73 if (diff <= QUICKSORT_THRESHOLD) {
74 break;
75 }
76 int i = (hi + lo) / 2;
77 if (compare(lo, i) > 0) {
78 swap(lo, i);
79 }
80 if (compare(lo, hi) > 0) {
81 swap(lo, hi);
82 }
83 if (compare(i, hi) > 0) {
84 swap(i, hi);
85 }
86 int j = hi - 1;
87 swap(i, j);
88 i = lo;
89 int v = j;
90 for (;;) {
91 while (compare(++i, v) < 0) {
92 ;
93 }
94 while (compare(--j, v) > 0) {
95 ;
96 }
97 if (j < i) {
98 break;
99 }
100 swap(i, j);
101 }
102 swap(i, hi - 1);
103 if (j - lo <= hi - i + 1) {
104 quickSortHelper(lo, j);
105 lo = i + 1;
106 } else {
107 quickSortHelper(i + 1, hi);
108 hi = j;
109 }
110 }
111 }
112
113 private void insertionSort(int lo, int hi) {
114 for (int i = lo + 1 ; i <= hi; i++) {
115 for (int j = i; j > lo; j--) {
116 if (compare(j - 1, j) > 0) {
117 swap(j - 1, j);
118 } else {
119 break;
120 }
121 }
122 }
123 }
124
125 protected void mergeSort(int lo, int hi) {
126 int diff = hi - lo;
127 if (diff <= MERGESORT_THRESHOLD) {
128 insertionSort(lo, hi);
129 return;
130 }
131 int mid = lo + diff / 2;
132 mergeSort(lo, mid);
133 mergeSort(mid, hi);
134 merge(lo, mid, hi, mid - lo, hi - mid);
135 }
136
137 private void merge(int lo, int pivot, int hi, int len1, int len2) {
138 if (len1 == 0 || len2 == 0) {
139 return;
140 }
141 if (len1 + len2 == 2) {
142 if (compare(pivot, lo) < 0) {
143 swap(pivot, lo);
144 }
145 return;
146 }
147 int first_cut, second_cut;
148 int len11, len22;
149 if (len1 > len2) {
150 len11 = len1 / 2;
151 first_cut = lo + len11;
152 second_cut = lower(pivot, hi, first_cut);
153 len22 = second_cut - pivot;
154 } else {
155 len22 = len2 / 2;
156 second_cut = pivot + len22;
157 first_cut = upper(lo, pivot, second_cut);
158 len11 = first_cut - lo;
159 }
160 rotate(first_cut, pivot, second_cut);
161 int new_mid = first_cut + len22;
162 merge(lo, first_cut, new_mid, len11, len22);
163 merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
164 }
165
166 private void rotate(int lo, int mid, int hi) {
167 int lot = lo;
168 int hit = mid - 1;
169 while (lot < hit) {
170 swap(lot++, hit--);
171 }
172 lot = mid; hit = hi - 1;
173 while (lot < hit) {
174 swap(lot++, hit--);
175 }
176 lot = lo; hit = hi - 1;
177 while (lot < hit) {
178 swap(lot++, hit--);
179 }
180 }
181
182 private int lower(int lo, int hi, int val) {
183 int len = hi - lo;
184 while (len > 0) {
185 int half = len / 2;
186 int mid= lo + half;
187 if (compare(mid, val) < 0) {
188 lo = mid + 1;
189 len = len - half -1;
190 } else {
191 len = half;
192 }
193 }
194 return lo;
195 }
196
197 private int upper(int lo, int hi, int val) {
198 int len = hi - lo;
199 while (len > 0) {
200 int half = len / 2;
201 int mid = lo + half;
202 if (compare(val, mid) < 0) {
203 len = half;
204 } else {
205 lo = mid + 1;
206 len = len - half -1;
207 }
208 }
209 return lo;
210 }
211 }
212 |
Popular Tags |
Java API By Example, From Geeks To Geeks.