앞서 배운 정렬 알고리즘들은.. (버블, 삽입, 선택)
작은 규모의 배열에서는 잘 작동하지만, 규모가 커질수록 잘 적용되지 않는다.
합병정렬 (Merge Sort)
0. 개요
배열을 더 작은 배열로 나누는 방식 (분할정복 알고리즘), 요소 배열이 0개나 1개가 될 때까지 반복
0개나 1개가 된 요소 배열 모음을 다시 병합함. 이 과정에서 정렬이 이루어짐.
예를 들어 8개의 원소를 가진 배열을 합병정렬하고자 한다면, 4 -> 2 -> 1개의 원소 그룹으로 나누고 1 -> 2 -> 4 -> 8개로 합치는 과정에서 정렬
1. 로직 구현
의사코드
- 정렬된 두 배열의 합병을 담당할 함수 구현. 입력 배열 두 개에 있는 모든 요소를 포함
- 초기값이 0인 I와 J 카운터를 두 배열에 각각 배치하여 While문을 통해 구현할 것을 추천
- 배열1[I]와 배열2[J]를 비교하여, 작은 값부터 결과 배열에 삽입. 삽입된 카운터의 값은 1 증가
- 이 과정을 반복하다 한 배열의 카운터가 배열 끝까지 돌았을 경우 다른 배열에 있는 남은 원소를 결과 배열에 삽입하고 종료
- 루프 종료 조건 : 둘 중 한 배열의 카운터가 배열의 끝에 도달한 경우
구현
function merge(arr1,arr2){
let results = [];
let i=0;
let j=0;
while(i < arr1.length && j < arr2.length){
if(arr1[i] < arr2[j]){
results.push(arr1[i]);
i++;
}
else{
results.push(arr2[j]);
j++;
}
}
while(i < arr1.length){
results.push(arr1[i])
i++;
}
while(j < arr2.length){
results.push(arr2[j])
j++;
}
return results;
}while문을 세 개나 썼다 ..
2. 정렬 구현
일반적으로 합병 정렬 구현 시 재귀함수를 이용한다.
의사코드
- 입력받은 배열을 반으로 나눠야 하는데, slice() 메서드를 활용
- 재귀함수를 사용해 (1)을 반복, 각 배열의 길이가 0 또는 1이 될 경우 종료
- 앞에서 구현한 합병 로직을 적용, 최종적으로 전부 합쳐진 배열을 반환
구현
function mergeSort(arr) {
// 재귀 종료 조건
if (arr.length <= 1) return arr;
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
console.log("Left : ", left);
console.log("right : ", right);
console.log(arr);
return merge(left, right);
}console.log는 코드 처리 과정에서 배열의 움직임을 시각적으로 확인하기 위해 디버깅한 것이고, 함수가 호출될 때마다 중간점을 설정, 이를 기준으로 좌/우 배열을 쪼개질 수 없을 때까지 나눈 후 병합시키며 정렬되는 알고리즘을 재귀함수를 통해 구현하였다.
합병정렬의 시공간 복잡도
합병정렬은 최선, 최악, 평균의 상황 모두에서 O(n log n) 복잡도를 갖는다. 이는 정렬하고자 하는 데이터의 형태에 영향을 미치지 않음을 뜻하며, 앞선 세 가지 방법의 정렬보다 준수한 성능을 보여준다.
n log n
복잡도 계산에서의 log는 암묵적으로 밑이 2인 거듭제곱을 의미한다. 합병정렬에서 입력으로 들어오는 배열 길이의 2거듭 제곱만큼 연산이 실행되기 때문에, log n으로 표현할 수 있다. 또한 병합 시 배열의 모든 원소를 한 번씩 순회하므로 O(n)의 연산이 수행된다. 따라서 이를 합해, n log n의 복잡도를 갖는다는 것을 확인할 수 있다.
