forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCombSort.java
More file actions
72 lines (64 loc) · 1.86 KB
/
CombSort.java
File metadata and controls
72 lines (64 loc) · 1.86 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
package com.thealgorithms.sorts;
/**
* Comb Sort algorithm implementation
*
* <p>
* Best-case performance O(n * log(n)) Worst-case performance O(n ^ 2)
* Worst-case space complexity O(1)
*
* <p>
* Comb sort improves on bubble sort.
*
* @author Sandeep Roy (https://github.com/sandeeproy99)
* @author Podshivalov Nikita (https://github.com/nikitap492)
* @see BubbleSort
* @see SortAlgorithm
*/
class CombSort implements SortAlgorithm {
private static final double SHRINK_FACTOR = 1.3;
/**
* Method to find the next gap
*
* @param gap the current gap
* @return the next gap value
*/
private int getNextGap(int gap) {
gap = (int) (gap / SHRINK_FACTOR);
return Math.max(gap, 1);
}
/**
* Method to sort the array using CombSort
*
* @param arr 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[] arr) {
int gap = arr.length;
boolean swapped = true;
while (gap != 1 || swapped) {
gap = getNextGap(gap);
swapped = performSwaps(arr, gap);
}
return arr;
}
/**
* Method to perform the swapping of elements in the array based on the current gap
*
* @param arr the array to be sorted
* @param gap the current gap
* @param <T> the type of elements in the array
* @return true if a swap occurred, false otherwise
*/
private <T extends Comparable<T>> boolean performSwaps(final T[] arr, final int gap) {
boolean swapped = false;
for (int i = 0; i < arr.length - gap; i++) {
if (SortUtils.less(arr[i + gap], arr[i])) {
SortUtils.swap(arr, i, i + gap);
swapped = true;
}
}
return swapped;
}
}