오늘 배운 것
합병 정렬(Merge Sort)
합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. <위키백과 정의>
- 큰 그림(fucntion mergeSort)
- 비교/합병 알고리즘(fucntion Merge)
그림출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
구체적인 개념
- 길이가 2 이상일 경우 하나의 배열을 두 개의 균등한 크기의 배열로 분할한다.(left, right)
- 두 개의 분할된 배열을 각각 정렬하고, 합병해서 전체가 정렬된 배열이 되게 한다.
- 중요한 점은 길이가 1이 될 때까지 분할하기만 하는 것이 아니라, 분할하면서 동시에 정렬이 이루어져야 하는 것이다.(결과적으로는 재귀를 사용하면 모두 분할된 다음 합병된다.)
- 첫번째 그림을 재귀적으로 이해해보자.(저 순서를 따라가는 알고리즘을 만들려고하지말고, 재귀를 사용하면 자연스럽게 저 순서를 따라가게 될 것이다. 잘 살펴보면 길이가 1인 배열로 분할된 상태를 기준으로 위와 아래가 데칼코마니다!!)
코드 구현(JavaScript)
- 제로초님 블로그를 많이많이 참고한 코드
//쪼개고 정리하는 함수
const mergeSort = function(array) {
//길이가 1이면 리턴
if(array.length===1){
return array
}
//길이가 1이 아니면 좌,우로 반 쪼개기
let half = Math.floor(array.length/2)
let left = array.slice(0, half)
let right = array.slice(half, array.length)
//재귀적으로 쪼개고, 합병정렬
return merge(mergeSort(left), mergeSort(right))
};
//비교 합병 함수
const merge = function (left, right){
//비교한 결과를 담을 배열 선언
let result = []
//왼쪽과 오른쪽 배열의 길이가 동시에 남아있을 동안 실행
while(left.length && right.length){
//각 배열의 첫번째 요소를 비교해서 새로운 배열에 넣기
if(left[0] < right[0]){
//shift()메소드는 배열의 첫번째 요소를 제거하고, 제거된 요소를 반환한다.
//result에는 왼쪽의 첫 번째요소가 생성되고, 왼쪽 배열에서는 제거될 것이다.(길이 -1)
result.push(left.shift())
}
//반대일 경우도 마찬가지
else{
result.push(right.shift())
}
}
//만약 한 쪽 배열이 먼저 끝난다면 남은 배열은 새로운 배열에 넣어준다.
while(left.length){
result.push(left.shift())
}
while(right.length){
result.push(right.shift())
}
//좌우 합병과 정렬이 모두 끝났으면 반환해준다.
return result
}참고문헌
다 늦은 밤, 달밤의 개발일기