Golang Algorithm - ShellSort (셸 정렬)

셸정렬이란?
가장 오래된 정렬 알고리즘 중 하나 알고리즘을 만든 사람 도널드 셸의이름을 따서 만든 정렬 
보완한 삽입정렬의 일반화로 볼 수 있음 

https://ko.wikipedia.org/wiki/%EC%85%B8_%EC%A0%95%EB%A0%AC

셸 정렬 - 위키백과, 우리 모두의 백과사전

ShellSort는 주로 삽입 정렬의 변형입니다. shellSort의 아이디어는 멀리 있는 물건들의 교환을 허용하는 것이다. shellSort에서 우리는 N의 큰 값에 대해 배열을 N 정렬로 만든다. 우리는 1이 될 때까지 N의 값을 계속 줄인다. 배열은 모든 N번째 요소의 모든 하위 목록이 정렬된 경우 N 정렬이라고 합니다.

 

 

go로 구현하는 셸 정렬

 

 함수의 역할

 

main() : 20개의 난수 배열을 생성하는 함수 generateSlice를 호출한 뒤 quicksort 함수를 호출하는 메인 함수

generateSlice() : slice를 초기화한뒤 slice 배열에 1부터 999까지의 난수 -  1부터 999까지의 난수를 계산한 원소를 삽인한 배열(slice)을 리턴한다. 

func shellsort():  함수 내부에서는 배열의 크기 n과 간격 배열 gaps을 초기화합니다. gaps 배열은 쉘 정렬에서 사용될 간격을 저장하며, 처음에는 간격 1만 포함합니다. 이후 k 변수를 이용하여 간격 배열을 계산합니다.

func element(): 지수 연산을 수행하여 간격 값을 계산합니다.

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {

	//난수 배열 생성
	slice := generateSlice(20)
	//정렬 전
	fmt.Println("\n--- Unsorted --- \n\n", slice)
	//쉘정렬 
	shellsort(slice)
	//정렬 후
	fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}

// 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 shellsort(items []int) {
	//n은 배열의 크기 설정, gaps 배열 설정 
    var (
        n = len(items)
        gaps = []int{1}
        k = 1
     
    )
     
    for {
        //k를 이용해서 간격 배열 계산 
        gap := element(2, k) + 1
        if gap > n-1 {
            break
        }
		
        gaps = append([]int{gap}, gaps...)
        k++
    }
     
    for _, gap := range gaps {
        for i := gap; i < n; i += gap {
            j := i
			//for문 j가 양수일 때 
            for j > 0 {
                if items[j-gap] > items[j] {
					//j-gap 인덱스가 j보다 크면 인덱스 위치 변경 
                    items[j-gap], items[j] = items[j], items[j-gap]
                }
				//j 값에 j - gap 대입 
                j = j - gap
            }
        }
    }
}
 
func element(a, b int) int {
    e := 1
    for b > 0 {
        if b&1 != 0 {
            e *= a
        }
        b >>= 1
        a *= a
    }
    return e
}

 

go 소스코드 출력 결과

go run shell_sort.go 

--- Unsorted --- 

 [196 322 -162 2 -323 249 -81 -89 -487 -139 -32 -683 -496 113 -162 -259 285 342 181 56]

--- Sorted ---

 [-683 -496 -487 -323 -259 -162 -162 -139 -89 -81 -32 2 56 113 181 196 249 285 322 342]