forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathShellSort.java
More file actions
69 lines (61 loc) · 1.79 KB
/
ShellSort.java
File metadata and controls
69 lines (61 loc) · 1.79 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
package com.thealgorithms.sorts;
public class ShellSort implements SortAlgorithm {
/**
* Implements generic shell sort.
*
* @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;
}
int gap = calculateInitialGap(array.length);
while (gap > 0) {
performGapInsertionSort(array, gap);
gap = calculateNextGap(gap);
}
return array;
}
/**
* Calculates the initial gap value using the Knuth sequence.
*
* @param length the length of the array.
* @return the initial gap value.
*/
private int calculateInitialGap(final int length) {
int gap = 1;
while (gap < length / 3) {
gap = 3 * gap + 1;
}
return gap;
}
/**
* Calculates the next gap value.
*
* @param currentGap the current gap value.
* @return the next gap value.
*/
private int calculateNextGap(final int currentGap) {
return currentGap / 3;
}
/**
* Performs an insertion sort for the specified gap value.
*
* @param array the array to be sorted.
* @param gap the current gap value.
* @param <T> the type of elements in the array.
*/
private <T extends Comparable<T>> void performGapInsertionSort(final T[] array, final int gap) {
for (int i = gap; i < array.length; i++) {
T temp = array[i];
int j;
for (j = i; j >= gap && SortUtils.less(temp, array[j - gap]); j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
}
}