Comb Sort - 빗질 정렬

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

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

Comb sort - Wikipedia

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

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

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

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

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

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