forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFlashSort.java
More file actions
206 lines (184 loc) · 7.39 KB
/
FlashSort.java
File metadata and controls
206 lines (184 loc) · 7.39 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
package com.thealgorithms.sorts;
/**
* Implementation of Flash Sort algorithm that implements the SortAlgorithm interface.
*
* Sorts an array using the Flash Sort algorithm.
* <p>
* Flash Sort is a distribution sorting algorithm that partitions the data into
* different classes based on a classification array. It performs the sorting by
* first distributing the data elements into different buckets (or classes) and
* then permuting these buckets into the sorted order.
* <p>
* The method works as follows:
* <ol>
* <li>Finds the minimum and maximum values in the array.</li>
* <li>Initializes a classification array `L` to keep track of the number of elements in each class.</li>
* <li>Computes a normalization constant `c1` to map elements into classes.</li>
* <li>Classifies each element of the array into the corresponding bucket in the classification array.</li>
* <li>Transforms the classification array to compute the starting indices of each bucket.</li>
* <li>Permutes the elements of the array into sorted order based on the classification.</li>
* <li>Uses insertion sort for the final arrangement to ensure complete sorting.</li>
* </ol>
*/
public class FlashSort implements SortAlgorithm {
private double classificationRatio = 0.45;
public FlashSort() {
}
public FlashSort(double classificationRatio) {
if (classificationRatio <= 0 || classificationRatio >= 1) {
throw new IllegalArgumentException("Classification ratio must be between 0 and 1 (exclusive).");
}
this.classificationRatio = classificationRatio;
}
public double getClassificationRatio() {
return classificationRatio;
}
public void setClassificationRatio(double classificationRatio) {
if (classificationRatio <= 0 || classificationRatio >= 1) {
throw new IllegalArgumentException("Classification ratio must be between 0 and 1 (exclusive).");
}
this.classificationRatio = classificationRatio;
}
/**
* Sorts an array using the Flash Sort algorithm.
*
* @param array the array to be sorted.
* @param <T> the type of elements to be sorted, must be comparable.
* @return the sorted array.
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
flashSort(array);
return array;
}
/**
* Sorts an array using the Flash Sort algorithm.
*
* @param arr the array to be sorted.
* @param <T> the type of elements to be sorted, must be comparable.
*/
private <T extends Comparable<? super T>> void flashSort(T[] arr) {
if (arr.length == 0) {
return;
}
final T min = findMin(arr);
final int maxIndex = findMaxIndex(arr);
if (arr[maxIndex].compareTo(min) == 0) {
return; // All elements are the same
}
final int m = (int) (classificationRatio * arr.length);
final int[] classificationArray = new int[m];
final double c1 = (double) (m - 1) / arr[maxIndex].compareTo(min);
classify(arr, classificationArray, c1, min);
transform(classificationArray);
permute(arr, classificationArray, c1, min, arr.length, m);
insertionSort(arr);
}
/**
* Finds the minimum value in the array.
*
* @param arr the array to find the minimum value in.
* @param <T> the type of elements in the array, must be comparable.
* @return the minimum value in the array.
*/
private <T extends Comparable<? super T>> T findMin(final T[] arr) {
T min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i].compareTo(min) < 0) {
min = arr[i];
}
}
return min;
}
/**
* Finds the index of the maximum value in the array.
*
* @param arr the array to find the maximum value index in.
* @param <T> the type of elements in the array, must be comparable.
* @return the index of the maximum value in the array.
*/
private <T extends Comparable<? super T>> int findMaxIndex(final T[] arr) {
int maxIndex = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i].compareTo(arr[maxIndex]) > 0) {
maxIndex = i;
}
}
return maxIndex;
}
/**
* Classifies elements of the array into the classification array classificationArray.
*
* @param arr the array to be classified.
* @param classificationArray the classification array holding the count of elements in each class.
* @param c1 the normalization constant used to map the elements to the classification array.
* @param min the minimum value in the array.
* @param <T> the type of elements in the array, must be comparable.
*/
private <T extends Comparable<? super T>> void classify(final T[] arr, final int[] classificationArray, final double c1, final T min) {
for (int i = 0; i < arr.length; i++) {
int k = (int) (c1 * arr[i].compareTo(min));
classificationArray[k]++;
}
}
/**
* Transforms the classification array classificationArray into the starting index array.
*
* @param classificationArray the classification array holding the count of elements in each class.
*/
private void transform(final int[] classificationArray) {
for (int i = 1; i < classificationArray.length; i++) {
classificationArray[i] += classificationArray[i - 1];
}
}
/**
* Permutes the array into sorted order based on the classification array classificationArray.
*
* @param arr the array to be permuted.
* @param classificationArray the classification array holding the count of elements in each class.
* @param c1 the normalization constant used to map the elements to the classification array.
* @param min the minimum value in the array.
* @param n the length of the array.
* @param m the number of classes in the classification array.
* @param <T> the type of elements in the array, must be comparable.
*/
private <T extends Comparable<? super T>> void permute(final T[] arr, final int[] classificationArray, final double c1, T min, int n, int m) {
int move = 0;
int j = 0;
int k = m - 1;
T flash;
while (move < n - 1) {
while (j > classificationArray[k] - 1) {
j++;
k = (int) (c1 * arr[j].compareTo(min));
}
flash = arr[j];
while (j != classificationArray[k]) {
k = (int) (c1 * flash.compareTo(min));
T temp = arr[classificationArray[k] - 1];
arr[classificationArray[k] - 1] = flash;
flash = temp;
classificationArray[k]--;
move++;
}
}
}
/**
* Sorts an array using the insertion sort algorithm.
*
* @param arr the array to be sorted.
* @param <T> the type of elements to be sorted, must be comparable.
*/
private <T extends Comparable<? super T>> void insertionSort(final T[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
T key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j].compareTo(key) > 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}