Golang Algorithm - mergeSort(병합정렬)

병합정렬이란? 

 

병합정렬 또는 합병정렬이라고 불린다. 비교 기반 정렬 알고리즘이고 분할정복 알고리즘의 하나다.

존 폰 노이만이 개발했다. 내가 볼 때는 중간 값을 구한뒤 왼쪽, 오른쪽 배열 요소를 순회를 하면서 값을 구하는 정렬 같은데 자세한 내용은 하단의 Go 소스코드를 보고 이해하면된다. 

다음은 위키 내용이다.

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

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

 

 

go로 구현하는 병합정렬

 

 함수의 역할

 

 

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

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

mergeSort() :  middle값을 구한 뒤 left, right 배열을 재귀호출로 부르면서 merge를 호출한다.
merge() : 

• result 초기화
• left, right 크기 비교 후 각 배열을 정렬함
• 이후 result에 left, right배열요소 삽입
• result 반환

 

go 소스 코드

package main

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

func main() {
	//난수 배열 생성 
	slice := generateSlice(20)
	//정렬 전 
	fmt.Println("--- Unsorted ---")
	//slice 출력 
	fmt.Println(slice)
	//정렬 후 
	fmt.Println("--- Sorted ---")
	//병합정렬 결과 
	fmt.Println(mergeSort(slice))
}

func generateSlice(size int) []int {
	//slice 초기화 
	slice := make([]int, size)
	//시간 동기화 
	rand.Seed(time.Now().UnixNano())
	//난수생성으로 배열 저장 
	for i := 0; i < size; i++ {
		slice[i] = rand.Int() % 1000 - 500
	}
	return slice
}

//병합정렬 
func mergeSort(items []int) []int {
	//2미만은 그대로 리턴 
	if len(items) < 2 {
		return items
	}

	//middle은 중간 값, middle을 기준으로 left, right 값 설정 
	middle := len(items) / 2
	
	left := mergeSort(items[:middle])
	right := mergeSort(items[middle:])

	//merge 반환 
	return merge(left, right)
}

//병합 함수
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))

	//left와 right 배열 크기가 0일 때 반복문 종료 
	for len(left) > 0 && len(right) > 0 {
		//left[0]가 작으면 result에 left[0]대입
		//left[1:]이후부터 모든 원소를 left 대입
		if left[0] < right[0] {
			result = append(result, left[0])
			left = left[1:]
		//right[0]이 더 클 경우 
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	//result에 left, right 삽입 
	result = append(result, left...)
	result = append(result, right...)

	//result 반환
	return result
}

 

go 소스코드 출력 결과

--- Unsorted ---
[-9 -406 -175 -500 358 -422 -231 -121 3 226 -364 -174 -370 165 219 73 -168 265 476 495]
--- Sorted ---
left [-9] right [-406]
left [-500] right [358]
left [-175] right [-500 358]
left [-406 -9] right [-500 -175 358]
left [-422] right [-231]
left [3] right [226]
left [-121] right [3 226]
left [-422 -231] right [-121 3 226]
left [-500 -406 -175 -9 358] right [-422 -231 -121 3 226]
left [-364] right [-174]
left [165] right [219]
left [-370] right [165 219]
left [-364 -174] right [-370 165 219]
left [73] right [-168]
left [476] right [495]
left [265] right [476 495]
left [-168 73] right [265 476 495]
left [-370 -364 -174 165 219] right [-168 73 265 476 495]
left [-500 -422 -406 -231 -175 -121 -9 3 226 358] right [-370 -364 -174 -168 73 165 219 265 476 495]
[-500 -422 -406 -370 -364 -231 -175 -174 -168 -121 -9 3 73 165 219 226 265 358 476 495]