Comb Sort - 빗질 정렬

버블 정렬과 비슷한 계념으로 비교 대상을 배열의 앞과 뒤에서부터 시작하며 그 간격을 좁혀가며 정렬하는 방법입니다.

https://en.wikipedia.org/wiki/Comb_sort

Comb sort - Wikipedia

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
package main
import "fmt"
func main() {
    arr := [10]int{9,1,2,8,6,7,5,3,0,4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    arrLen := len(arr)
    gap := arrLen
    for gap > 1 {
        gap = gap * 10 / 13 //shrink factor is 1.3
        for i := 0; i+gap < arrLen; i++ {
            if arr[i] <= arr[i+gap] {
                arr[i], arr[i+gap] = arr[i+gap], arr[i]
            }
        }
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

각 코드에 대한 설명을 주석으로 달았습니다.

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
package main
import (
    "fmt"
)
func main() {
    arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    // 배열의 길이를 확인합니다.
    arrLen := len(arr)
    // 비교 간격으로 사용할 gap을 배열의 길이로 우선 초기화 합니다.
    gap := arrLen
    for gap > 1 {
        // 비교 간격을 줄이기 위한 shrink factor를 지정합니다.
        // shrink factor는 int 타입으로 길이가 10인 배열의 경우 7, 5, 3, 2, 1로 줄어듭니다.
        gap = gap * 10 / 13
        // i+gap이 배열의 길이보다 작다면 for loop를 계속 실행합니다.
        for i := 0; i+gap < arrLen; i++ {
            // 0부터 순차젹으로 증가하는 배열의 자릿수 값과 i부터 gap만큼 떨어진 값을 비교합니다.
            if arr[i] >= arr[i+gap] {
                // 오름차순일 경우 i자리의 값이 크다면 비교한 자릿수의 값과 바꿔놓습니다.
                arr[i], arr[i+gap] = arr[i+gap], arr[i]
            }
        }
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

다른 comb sort 예제들도 비슷하네요.

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
package main
import (
    "fmt"
    "math/rand"
    "time"
)
func main() {
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    combsort(slice)
    fmt.Println("\n--- Sorted ---\n\n", slice)
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
    slice := make([]int, size, size)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < size; i++ {
        slice[i] = rand.Intn(999) - rand.Intn(999)
    }
    return slice
}
func combsort(items []int) {
    var (
        n       = len(items)
        gap     = len(items)
        shrink  = 1.3
        swapped = true
    )
    for swapped {
        swapped = false
        gap = int(float64(gap) / shrink)
        if gap < 1 {
            gap = 1
        }
        for i := 0; i+gap < n; i++ {
            if items[i] > items[i+gap] {
                items[i+gap], items[i] = items[i], items[i+gap]
                swapped = true
            }
        }
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX