Merge Sort 합병정렬

티스토리 뷰

ALGORITHM/Theory

Merge Sort 합병정렬

Harimad 2022. 4. 28. 15:38

기가 막히게 빠른 정렬 소개
합병 정렬 : 소개
배열 합병 소개
배열 합병 : 구현
합병 정렬 작성하기 1부
합병 정렬 작성하기 2부
합병 정렬을 위한 빅오 복잡도

cs50

기가 막히게 빠른 정렬 소개

슬라이드

visualgo : https://visualgo.net/en/sorting

Sorting Algorithms Animations : https://www.toptal.com/developers/sorting-algorithms

합병 정렬 : 소개

1. 합병정렬은 합병(merging)과 분류(sorting)라는 두 가지의 조합이다!

2. 길이가 0 또는 1인 요소의 배열이 항상 정렬되어 있다는 사실을 활용한다.

3. 배열을 길이가 0 또는 1인 요소의 더 작은 배열로 분해한 다음, 새로 정렬된 배열을 빌드하는 방식으로 작동한다(분류 -> 합병).

동작 방법?

분할

정렬

배열 합병 소개

1. 병합 정렬을 구현하려면 먼저 정렬된 두 배열을 병합하는 기능을 구현하는 것이 유용하다.

2. 정렬된 두 배열이 주어지면, helper함수는 정렬된 두 입력 배열의 모든 요소로 구성된 새 배열을 생성해야 한다.

3. 이 기능은 O(n + m) 시간 및 O(n + m) 공간 복잡도에서 실행되어야 하며 전달된 파라미터를 수정해서는 안된다.

배열 합병 의사코드

1. 빈 배열을 만들고 각 입력 배열에서 가장 작은 값을 살펴본다.

2-1. 첫 번째 배열의 값이 두 번째 배열의 값보다 작으면 첫 번째 배열의 값을 결과에 밀어넣고 첫 번째 배열의 다음 값으로 이동한다.
2-2. 첫 번째 배열의 값이 두 번째 배열의 값보다 크면 두 번째 배열의 값을 결과에 밀어넣고 두 번째 배열의 다음 값으로 이동한다.
2-3. 한 배열이 소진되면 다른 배열의 나머지 값을 모두 밀어 넣는다.

배열 합병 예시

 // 배열 합병 예시
 _            _
[2, 4, 6, 8] [1, 3, 5, 7]
answer : [1]

 _            _ 
[2, 4, 6, 8] [3, 5, 7]
answer : [1, 2]

 _         _
[4, 6, 8] [3, 5, 7]
answer : [1, 2, 3]

 _         _
[4, 6, 8] [5, 7]
answer : [1, 2, 3, 4]

 _      _
[6, 8] [5, 7]
answer : [1, 2, 3, 4, 5]

 _      _ 
[6, 8] [7]
answer : [1, 2, 3, 4, 5, 6]

_    _
[8] [7]
answer : [1, 2, 3, 4, 5, 6, 7]

_
[8]
answer : [1, 2, 3, 4, 5, 6, 7, 8]

배열 합병 : 구현

// Merges two already sorted arrays
function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            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;
}
merge([100,200], [1,2,3,5,6])

합병 정렬 작성하기 1부

합병정렬(mergeSort) 의사코드

1. 배열이 비어 있거나 하나의 요소가 있을 때까지 배열을 반으로 나눈다.

2. 정렬된 배열이 더 작으면 배열의 전체 길이로 돌아갈 때까지 다른 정렬된 배열과 병합한다.

3. 배열이 다시 병합되면 병합된(및 정렬됨!) 배열을 반환한다.

합병 정렬 작성하기 2부

// Merge function from earlier
function merge(arr1, arr2){
    // 위에 있음
}

// Recrusive Merge Sort
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));
    return merge(left, right);
}

mergeSort([10,24,76,73]);