Golang Algorithm - CombSort (빗질 정렬)

 

빗질 정렬이란?
버블정렬을 개선한 정렬알고리즘으로 리스트 끝에 있는 작은 값들을 제거하기 위한 아이디어가 추가된 알고리즘

https://ko.wikipedia.org/wiki/%EB%B9%97%EC%A7%88_%EC%A0%95%EB%A0%AC

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

 

 

go로 구현하는 빗질 정렬

 

 함수의 역할

 

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

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

combsort() :  빗질정렬 

• n, gap, shrink, swapped 변수 설정 
• 빗질정렬을 위한 gap 밸류 업데이트
• 배열 크기만큼 순회를 한 뒤 i, i+gap의 인덱스의 원소를 비교하고 원소 위치 교환

 

go 소스 코드

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, "\n")
}

//난수 배열 생성 
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 //gap을 축소해주는 계수 설정 
		swapped = true //swap 판단 값
	)
	
	for swapped {
		swapped = false
			//다음 정렬을 위한 gap 밸류 업데이트 
        	gap = int(float64(gap) / shrink)
			//갭이 1 미만이면 
        	if gap < 1 {
				//갭은 1 
			gap = 1
		}
		//반복 순회 특이점은 i에 gap을 더함  
		for i := 0; i+gap < n; i++ {
			//아이템 배열에서 i 인덱스가 i + gap 인덱스보다 크면 인덱스 위치 교환
			if items[i] > items[i+gap] {
				items[i+gap], items[i] = items[i], items[i+gap]
				//스왑=true 
				swapped = true
			}	
		}
	}
}

 

 

go 소스코드 실행 로그 출력

go run comb_sort.go 

--- Unsorted --- 

 [61 50 -447 186 29 25 -742 530 -377 261 -440 508 -159 -529 299 -140 450 -677 352 737]

--- Sorted ---

 [-742 -677 -529 -447 -440 -377 -159 -140 25 29 50 61 186 261 299 352 450 508 530 737]