-
-
Notifications
You must be signed in to change notification settings - Fork 2.5k
/
combSort.go
33 lines (28 loc) · 701 Bytes
/
combSort.go
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
// Implementation of comb sort algorithm, an improvement of bubble sort
// Reference: https://www.geeksforgeeks.org/comb-sort/
package sort
import "github.com/TheAlgorithms/Go/constraints"
func getNextGap(gap int) int {
gap = (gap * 10) / 13
if gap < 1 {
return 1
}
return gap
}
// Comb is a simple sorting algorithm which is an improvement of the bubble sorting algorithm.
func Comb[T constraints.Ordered](data []T) []T {
n := len(data)
gap := n
swapped := true
for gap != 1 || swapped {
gap = getNextGap(gap)
swapped = false
for i := 0; i < n-gap; i++ {
if data[i] > data[i+gap] {
data[i], data[i+gap] = data[i+gap], data[i]
swapped = true
}
}
}
return data
}