Gnome Sort - 난쟁이 정렬

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

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

 

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

Gnome sort - Wikipedia

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

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

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

 

Go로 구현한 코드입니다.

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)
}

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

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)
}

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

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

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++
	}
}

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