forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSpreadSort.java
More file actions
273 lines (249 loc) · 9.42 KB
/
SpreadSort.java
File metadata and controls
273 lines (249 loc) · 9.42 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
package com.thealgorithms.sorts;
import java.util.Arrays;
/**
* SpreadSort is a highly efficient sorting algorithm suitable for large datasets.
* It distributes elements into buckets and recursively sorts these buckets.
* This implementation is generic and can sort any array of elements that extend Comparable.
*/
public class SpreadSort implements SortAlgorithm {
private static final int MAX_INSERTION_SORT_THRESHOLD = 1000;
private static final int MAX_INITIAL_BUCKET_CAPACITY = 1000;
private static final int MAX_MIN_BUCKETS = 100;
private final int insertionSortThreshold;
private final int initialBucketCapacity;
private final int minBuckets;
/**
* Constructor to initialize the SpreadSort algorithm with custom parameters.
*
* @param insertionSortThreshold the threshold for using insertion sort for small segments (1-1000)
* @param initialBucketCapacity the initial capacity for each bucket (1-1000)
* @param minBuckets the minimum number of buckets to use (1-100)
*/
public SpreadSort(int insertionSortThreshold, int initialBucketCapacity, int minBuckets) {
if (insertionSortThreshold < 1 || insertionSortThreshold > MAX_INSERTION_SORT_THRESHOLD) {
throw new IllegalArgumentException("Insertion sort threshold must be between 1 and " + MAX_INSERTION_SORT_THRESHOLD);
}
if (initialBucketCapacity < 1 || initialBucketCapacity > MAX_INITIAL_BUCKET_CAPACITY) {
throw new IllegalArgumentException("Initial bucket capacity must be between 1 and " + MAX_INITIAL_BUCKET_CAPACITY);
}
if (minBuckets < 1 || minBuckets > MAX_MIN_BUCKETS) {
throw new IllegalArgumentException("Minimum number of buckets must be between 1 and " + MAX_MIN_BUCKETS);
}
this.insertionSortThreshold = insertionSortThreshold;
this.initialBucketCapacity = initialBucketCapacity;
this.minBuckets = minBuckets;
}
/**
* Default constructor with predefined values.
*/
public SpreadSort() {
this(16, 16, 2);
}
/**
* Sorts an array using the SpreadSort algorithm.
*
* @param array the array to be sorted
* @param <T> the type of elements in the array
* @return the sorted array
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
if (array.length == 0) {
return array;
}
spreadSort(array, 0, array.length - 1);
return array;
}
/**
* Internal method to sort an array segment using the SpreadSort algorithm.
*
* @param array the array to be sorted
* @param left the left boundary of the segment
* @param right the right boundary of the segment
* @param <T> the type of elements in the array
*/
private <T extends Comparable<T>> void spreadSort(final T[] array, final int left, final int right) {
if (left >= right) {
return;
}
// Base case for small segments
if (right - left < insertionSortThreshold) {
insertionSort(array, left, right);
return;
}
T min = findMin(array, left, right);
T max = findMax(array, left, right);
if (min.equals(max)) {
return; // All elements are the same
}
int numBuckets = calculateNumBuckets(right - left + 1);
final Bucket<T>[] buckets = createBuckets(numBuckets);
distributeElements(array, left, right, min, max, numBuckets, buckets);
collectElements(array, left, buckets);
}
/**
* Finds the minimum element in the specified segment of the array.
*
* @param array the array to search
* @param left the left boundary of the segment
* @param right the right boundary of the segment
* @param <T> the type of elements in the array
* @return the minimum element
*/
private <T extends Comparable<T>> T findMin(final T[] array, final int left, final int right) {
T min = array[left];
for (int i = left + 1; i <= right; i++) {
if (SortUtils.less(array[i], min)) {
min = array[i];
}
}
return min;
}
/**
* Finds the maximum element in the specified segment of the array.
*
* @param array the array to search
* @param left the left boundary of the segment
* @param right the right boundary of the segment
* @param <T> the type of elements in the array
* @return the maximum element
*/
private <T extends Comparable<T>> T findMax(final T[] array, final int left, final int right) {
T max = array[left];
for (int i = left + 1; i <= right; i++) {
if (SortUtils.greater(array[i], max)) {
max = array[i];
}
}
return max;
}
/**
* Calculates the number of buckets needed based on the size of the segment.
*
* @param segmentSize the size of the segment
* @return the number of buckets
*/
private int calculateNumBuckets(final int segmentSize) {
int numBuckets = segmentSize / insertionSortThreshold;
return Math.max(numBuckets, minBuckets);
}
/**
* Creates an array of buckets.
*
* @param numBuckets the number of buckets to create
* @param <T> the type of elements in the buckets
* @return an array of buckets
*/
@SuppressWarnings("unchecked")
private <T extends Comparable<T>> Bucket<T>[] createBuckets(final int numBuckets) {
final Bucket<T>[] buckets = new Bucket[numBuckets];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new Bucket<>(initialBucketCapacity);
}
return buckets;
}
/**
* Distributes elements of the array segment into buckets.
*
* @param array the array to be sorted
* @param left the left boundary of the segment
* @param right the right boundary of the segment
* @param min the minimum element in the segment
* @param max the maximum element in the segment
* @param numBuckets the number of buckets
* @param buckets the array of buckets
* @param <T> the type of elements in the array
*/
private <T extends Comparable<T>> void distributeElements(final T[] array, final int left, final int right, final T min, final T max, final int numBuckets, final Bucket<T>[] buckets) {
final double range = max.compareTo(min);
for (int i = left; i <= right; i++) {
final int scaleRangeDifference = array[i].compareTo(min) * numBuckets;
int bucketIndex = (int) (scaleRangeDifference / (range + 1));
buckets[bucketIndex].add(array[i]);
}
}
/**
* Collects elements from the buckets back into the array.
*
* @param array the array to be sorted
* @param left the left boundary of the segment
* @param buckets the array of buckets
* @param <T> the type of elements in the array
*/
private <T extends Comparable<T>> void collectElements(final T[] array, final int left, final Bucket<T>[] buckets) {
int index = left;
for (Bucket<T> bucket : buckets) {
if (bucket.size() > 0) {
T[] bucketArray = bucket.toArray();
spreadSort(bucketArray, 0, bucketArray.length - 1);
for (T element : bucketArray) {
array[index++] = element;
}
}
}
}
/**
* Insertion sort implementation for small segments.
*
* @param array the array to be sorted
* @param left the left boundary of the segment
* @param right the right boundary of the segment
* @param <T> the type of elements in the array
*/
private <T extends Comparable<T>> void insertionSort(final T[] array, final int left, final int right) {
for (int i = left + 1; i <= right; i++) {
T key = array[i];
int j = i - 1;
while (j >= left && SortUtils.greater(array[j], key)) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
/**
* Bucket class to hold elements during sorting.
*
* @param <T> the type of elements in the bucket
*/
private static class Bucket<T extends Comparable<T>> {
private T[] elements;
private int size;
/**
* Constructs a new bucket with initial capacity.
*/
@SuppressWarnings("unchecked")
Bucket(int initialBucketCapacity) {
elements = (T[]) new Comparable[initialBucketCapacity];
size = 0;
}
/**
* Adds an element to the bucket.
*
* @param element the element to add
*/
void add(T element) {
if (size == elements.length) {
elements = Arrays.copyOf(elements, size * 2);
}
elements[size++] = element;
}
/**
* Returns the number of elements in the bucket.
*
* @return the size of the bucket
*/
int size() {
return size;
}
/**
* Returns an array containing all elements in the bucket.
*
* @return an array containing all elements in the bucket
*/
@SuppressWarnings("unchecked")
T[] toArray() {
return Arrays.copyOf(elements, size);
}
}
}