Shell Sort - 쉘 정렬

Shell Sort는 삽입 정렬(Insertion Sort)을 보완한 정렬 방법입니다.
삽입정렬에서 언급했듯이 어느정도 정렬이 되어 있으면 효율이 높게 나옵니다.

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

Shellsort - Wikipedia

정렬 효율을 높이기 위해 간격을 나눠 정렬하는 방식입니다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog

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("")

	// 계속해서 중앙값을 찾습니다. 배열의 길이가 10이라면 5, 2, 1이 됩니다.
	// 중앙값 d는 조건 검색할 간격이 됩니다.
	for d := int(len(arr) / 2); d > 0; d /= 2 {

		// 중앙값에서 배열의 길이(마지막 인덱스)까지 값을 증가시킵니다.
		for i := d; i < len(arr); i++ {

			// 순차적으로 간격에 따라 비교 정렬합니다.
			for j := i; j >= d && arr[j-d] > arr[j]; j -= d {
				arr[j], arr[j-d] = arr[j-d], arr[j]
			}
		}
	}

	fmt.Println("Sorted array is: ", arr)

	// 정렬된 배열일 경우 왼쪽 끝자리와 오른쪽 끝자리의 값을 교환하며 오름/내림 차순으로 변환합니다.
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}

	fmt.Println("Reversed array is: ", arr)
}

위 코드에서 3 단계로된 for loop에 대해 바로 머리속에서 그려지지 않았습니다.
그래서 따로 정리해 봤습니다.

package main

import "fmt"

func main() {
	arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}

	for d := int(len(arr) / 2); d > 0; d /= 2 {
		for i := d; i < len(arr); i++ {
			for j := i; j >= d; j -= d {
				fmt.Println(j-d, j)
			}
		}
	}
}

위 코드에서 확인해 보면 처음 5의 간격으로 확인하고, 그다음 2의 간격, 그리고 1의 간격으로 확인하게 됩니다.
굳이 써보자면 아래와 같습니다.

다른 방법도 찾아봤습니다.

package main

import "fmt"

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")

	shellSort(arr)

	fmt.Println("Sorted array is: ", arr)

	// 정렬된 배열일 경우 왼쪽 끝자리와 오른쪽 끝자리의 값을 교환하며 오름/내림 차순으로 변환합니다.
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}

	fmt.Println("Reversed array is: ", arr)
}

func shellSort(slice []int) {
	size := len(slice)
	gap := 1
	var j int

	for gap < size {
		gap = 3*gap + 1
	}

	for gap > 1 {
		gap = gap / 3
		for index := gap; index < size; index++ {
			value := slice[index]
			j = index - gap

			for j >= 0 && value < slice[j] {
				slice[j+gap] = slice[j]
				j = j - gap
			}
			slice[j+gap] = value
		}
	}
}