/
ShellSort.java
93 lines (87 loc) · 2.86 KB
/
ShellSort.java
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
package com.jwetherell.algorithms.sorts;
import java.util.ArrayList;
import java.util.List;
/**
* Shellsort, also known as Shell sort or Shell's method, is an in-place
* comparison sort. It generalizes an exchanging sort, such as insertion or
* bubble sort, by starting the comparison and exchange of elements with
* elements that are far apart before finishing with neighboring elements.
* Starting with far apart elements can move some out-of-place elements into
* position faster than a simple nearest neighbor exchange.
* <p>
* Family: Exchanging.<br>
* Space: In-place.<br>
* Stable: False.<br>
* <p>
* Average case = depends on the gap<br>
* Worst case = O(n * log^2 n)<br>
* Best case = O(n)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Shell_sort">Shell Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class ShellSort<T extends Comparable<T>> {
private ShellSort() { }
public static <T extends Comparable<T>> T[] sort(int[] shells, T[] unsorted) {
for (int gap : shells) {
// Allocate arrays
List<List<T>> subarrays = new ArrayList<List<T>>(gap);
for (int i = 0; i < gap; i++) {
subarrays.add(new ArrayList<T>(10));
}
// Populate sub-arrays
int i = 0;
int length = unsorted.length;
while (i < length) {
for (int j = 0; j < gap; j++) {
if (i >= length)
continue;
T v = unsorted[i++];
List<T> list = subarrays.get(j);
list.add(v);
}
}
// Sort all sub-arrays
sortSubarrays(subarrays);
// Push the sub-arrays into the int array
int k = 0;
int iter = 0;
while (k < length) {
for (int j = 0; j < gap; j++) {
if (k >= length)
continue;
unsorted[k++] = subarrays.get(j).get(iter);
}
iter++;
}
}
return unsorted;
}
private static <T extends Comparable<T>> void sortSubarrays(List<List<T>> lists) {
for (List<T> list : lists) {
sort(list);
}
}
/**
* Insertion sort
*
* @param list
* List to be sorted.
*/
private static <T extends Comparable<T>> void sort(List<T> list) {
int size = list.size();
for (int i = 1; i < size; i++) {
for (int j = i; j > 0; j--) {
T a = list.get(j);
T b = list.get(j - 1);
if (a.compareTo(b) < 0) {
list.set(j - 1, a);
list.set(j, b);
} else {
break;
}
}
}
}
}