알고리즘 문제풀이 7
mergesort(합병정렬) 구현에 대한 알고리즘이다.
mergesort란?
합병정렬에 대한 설명(참고 블로그)
즉 주어진 배열을 각각의 개별 요소로 이루어진 배열이 될 때까지, 둘로 쪼개는 과정을 진행한다.
그리고 다 쪼개진 요소들을 크기 비교하여 합쳐준다.
즉 합병할 때, 실제 정렬이 이루어진다고 해서 합병정렬이라 부른다.
(개인적으로 해당 정렬의 효율적인 측면에서 조금 이해가 가지 않는다.)
->하나의 배열이 쪼개지고 다시 합쳐지는 과정이 재귀적으로 이루어진다.
(두 부분 리스트로 나누어지기 전까지)
->두 부분 리스트가 되었을때, 두개의 배열을 순회하면서 각 인덱스의 요소들을 크기 비교하여
더 작은 수를 먼저 새로운 배열에 넣어준다.
(가령, 1부분 리스트의 첫번째 요소 VS 2부분 리스트의 첫번째 요소에서 1부분 리스트의 요소가
더 작으면 해당 요소를 가상의 리스트에 넣어주고,
1부분 리스트의 두번째요소 VS 2부분 리스트의 첫번째 요소를 비교해서 더 작은 요소를 넣어주는 방식)
//우선 주어진 배열을 중간 인덱스 값을 기준으로 쪼개준다.
var mergeSort = function(array) {
// 재귀함수 탈출조건 단일 요소로 구성된 배열이라면, 리턴
if (array.length === 1) {
return array;
}
let middle = Math.floor(array.length / 2); // 배열의 중간 값
let left = array.slice(0, middle); // left side items
let right = array.slice(middle); // right side items
return merge(mergeSort(left), mergeSort(right));
//이 부분에서 궁금 한것이, 각 쪼개진 요소들이 완전히 쪼개지고 합병 작업이 들어갈까? 아니면
//동시다발적으로 이루어 질까? 즉 쪼개진 요소들의 크기비교 합병과, 각 부분 배열들의 쪼개짐이 말이다.
//정답은 쪼개지는 작업우선으로 이루어진다. (디버깅 진행해보니 알게 됨)
//위의 참고 블로그의 그림처럼 실제로 요소가 각 하나로 쪼개진 후에 merge 작업이 시작된다.
//각 배열들이 쪼개지고 왼쪽 배열과 오른쪽 배열은 크기 비교후 합병 작업으로 들어간다.
//그와 동시에 각 부분 배열들이 요소가 한개가 될때까지 쪼개지는 작업과 합병 작업이 동시에 이루어진다.
//이때, mergesort에 들어가는 배열의 길이가 1개일 경우, return merge(array)가 아니라,
//그냥 return array 인 이유는, 요소가 진짜 단 하나일 경우, 크기 비교할 이유가 없기 때문이다.
}
//왼쪽과 오른쪽 값을 비교하는 함수
function merge(left, right) {
let result = []; //크기 비교후 각 요소를 담을 결과 배열
let leftIndex = 0;
let rightIndex = 0;
// left items와 right items 비교
while(leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex))
}
디버깅을 통한 위의 코드의 구현 순서
가상의 배열 [27,34,8,2,15,10]
1. mergesort 함수를 통해서 해당 함수가 계속 쪼개진다.
그리고 요소가 각 한개로 쪼개진 [34],[8]에 대해 먼저 크기 비교를 시작한다.
2. merge 함수를 통해서 크기 비교후, result = [8,34]가 된다.
3. 그리고 mergesort 에서 [27]과 그 오른쪽 부분 배열이 비교되는데, 이 때,
merge 함수를 통해 크기 비교후 재정렬되어서 리턴된 함수가 [27]과 비교될 오른쪽 배열로서
리턴되어 값이 바뀌어서, [27]과 정렬된 [8,34]가 비교된다.
즉, 합병 및 크기비교 함수를 통해서, 재정렬된 함수가 반영되어서 다른 부분 배열들과 비교되고
그렇게 합병되어 가는 부분이 핵심인듯 하다.
mergeSort의 효율성
- 생긴 것과는 다르게(즉 복잡하지만) 효율적인 정렬이다.
-> 연결리스트와 사용된다면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
따라서 효율적이다.
why? (해당 부분이 잘 이해가 가지 않는다)
연결리스트를 사용하지 않는 경우, 두 집합을 서로 비교하여 정렬된 상태로 합친걸 잠시 옮겨둘 배열 또는 리스트가 필요하다.
하지만 레코드를 '연결 리스트'로 구성하여 구현할 경우
쪼개고, 합치고, 정렬할 때 포인터 값만 수정해주면 되므로 새로운 배열을 만들어서 재선언해줄 필요가 없다.
mergeSort의 시간복잡도
- 분할단계는 단순히 분할을 하므로 별도의 연산이 수행되지 않아서, 시간 복잡도를 계산할 필요가 없다.
- 합병 비교 단계
1) 합병단계는 일종의 트리구조로 비유해서 생각하면 그 단계의 깊이만큼의 시간복잡도를 가진다.
합병정렬은 주어진 배열을 둘 씩 쪼개고 다시 합치는 과정이기 때문에, 각 쪼개진 배열이
다시 합쳐지는 단계의 수는 log₂n 이다.
즉, n이 배열의 갯수라고 가정했을 때, 2^단계의수 = 배열의 갯수 가 되는 것.
2) 비교 정렬의 단계는 최악의 경우를 고려했을 때 당연히, n이다.
따라서 시간 복잡도는 nlog₂n이다.
Author And Source
이 문제에 관하여(알고리즘 문제풀이 7), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyunju-song/알고리즘-문제풀이-7저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)