Gnome Sort - 난쟁이 정렬

왜 난쟁이 정렬이라고 했는지는 모르지만 처음 불릴때는 stupid sort라고 했다고 합니다.

성능면에서는 별로 좋지 못한 정렬 알고리즘입니다.

 

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

Gnome sort - Wikipedia

정렬할 배열의 처음 기준 자리(index)를 1부터 시작합니다.

오름차순일 경우 왼쪽자리의 값이 클 경우 두 값의 자리를 변경하고 index를 하나 낮춰 같은 작업을 반복합니다.

만약 왼쪽자리의 값이 작을 경우 index를 하나 높여 같은 작업을 반복합니다.

 

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("")
    i := 1
    for i < len(arr) {
        if arr[i-1] < arr[i] {
            i++
        } else {
            arr[i], arr[i-1] = arr[i-1], arr[i]
            if i > 1 {
                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
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("")
    // 정렬할 배열의 기준 자리를 1번으로 합니다.
    i := 1
    // 배열의 길이가 기준 자리보다 작을때만 실행됩니다.
    for i < len(arr) {
        // 오름차순의 경우 기준자리의 왼쪽의 값이 기준자리보다 작을경우 기준자리를 하나 높여줍니다.
        if arr[i-1] < arr[i] {
            i++
            // 그렇지 않다면 (기준자리보다 왼쪽의 값이 높다면) 기준자리와 위치를 바꿔줍니다.
        } else {
            arr[i], arr[i-1] = arr[i-1], arr[i]
            // 기줁리가 1보가 크다면 기준자리를 하나 낮춥니다.
            if i > 1 {
                i--
            }
        }
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

다른 코드도 확인해 봤습니다.

Loop 안에서 배열의 시작접을 다시 잡는 j 변수를 넣고 continue Keyward를 사용했네요.

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 := []int{170, 45, 75, -90, -802, 24, 2, 66}
    fmt.Println("before:", arr)
    gnomeSort(arr)
    fmt.Println("after: ", arr)
}
func gnomeSort(arr []int) {
    for i, j := 1, 2; i < len(arr); {
        if arr[i-1] > arr[i] {
            arr[i-1], arr[i] = arr[i], arr[i-1]
            i--
            if i > 0 {
                continue
            }
        }
        i = j
        j++
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

성능은 좋지 않지만 코드가 간단해서 이해하기 쉽네요.