10 합병 정렬

  지금까지 공부했던 정렬들은 일반적인 정렬 알고리즘이었다. 이제는 보다 효율적인 정렬 알고리즘들에 대한 설명이다. 합병 정렬은 정확하게 말하면 분해와 합병을 하는 과정으로 정렬이 이뤄진다. 합병 정렬은 0개의 요소 또는 1개의 요소는 이미 정렬이 되어있다는 것을 활용하는 정렬 알고리즘이다. 즉 정렬되어 있지 않은 배열을 요소가 1개 또는 0개가 될 때까지 배열을 분할한 후 다시 정렬하면서 합병하는 것이다.(1개 또는 0개의 요소를 가지는 배열은 이미 정렬이 되어 있는 것이기 때문이다.)

 

  우선 합병 정렬 알고리즘을 구현하기 위해서는 정렬되어 있는 두 배열을 합병하는 방법을 알아야 한다. 

 

10.1 정렬된 두 배열 합병

의사코드

1. 우선 배열 두 개를 인수로 받는 함수를 정의하고, 마지막에 반환할 빈 배열을 변수에 저장한다.

2. 두 배열의 인덱스를 각각 i,j 포인터로 만들고 반복문을 활용한다.(while문을 사용하는것이 좋다)

3. 인수로 전달 받은 각 배열의 첫 번째 요소부터 비교를 시작한다.

4. 아직 살펴보지 않은 값이 있다면, 즉 i와 j가 각각의 배열 끝에 도달하지 않았다면, 첫 번째 배열의 값으로 첫 번째 요소를 취한 다음 두 번째 배열의 첫 번째 요소와 비교한다. 비교한 요소 중 더 작은 값을 변수에 저장한 빈 배열에 할당하고 할당을 한 배열의 인덱스 포인터에 1을 더하여 다른 배열과 다시 비교한다. 그리고 두 배열의 길이가 같지 않을 수 있으므로 두 배열내의 비교가 모두 끝난 후 아직 비교하지 못한 나머지 요소들을 빈 배열에 할당한다.(이미 다 정렬이 되어 있는 상태이기 때문에 다 넣어도 정렬된다.)

 

function mergeArray(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(arr[i]);
        i++;
    }
    while(j < arr2.length){
        results.push(arr2[j]); //비교 되지 못한 나머지 요소들 처리하기
        j++;
    }
    return results;
}

  이렇게 하면 정렬이 되어 있는 두 배열을 합병하는 알고리즘이 된다. 중요한것은 이미 정렬이 되어 있는 상태의 배열이어야 정렬되면서 하나의 배열을 만들 수 있는 것이다! 그렇기 때문에 합병 정렬 알고리즘에서 정렬된 상태를 만들기 위해 분할하는 것이다. 이제 합병 정렬을 구현해 보자

 

10.2 합병 정렬 구현

  이제 정렬된 두 배열을 합병하는 방법을 알았으니, 이제 배열을 계속 나누는 작업이 이뤄져야 한다. 이 경우에는 Array.prototype.slice메서드를 이용하는 것이 좋다. arr.slice메서드는 첫 번째 인수로 받은 인덱스부터 두 번째 인수로 받은 인덱스까지 배열을 복사하여 반환해 준다. 여기서 중요한 것은 배열의 요소가 0개 또는 1개를 가질때까지 계속 나눠야 한다는 것이다. 그 다음 정렬된 배열을 합병하는 위에 구현해 놓은 mergeArray함수를 이용하여 정렬하면서 합병하는 것이다. 대부분의 합병 정렬 구현시 재귀가 사용되기 때문에 이해하는데 어려움이 있을 수 있으나, 천천히 따라오면 충분히 이해할 수 있다.

function mergeArray(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(arr[i]);
        i++;
    }
    while(j < arr2.length){
        results.push(arr2[j]); //비교 되지 못한 나머지 요소들 처리하기
        j++;
    }
    return results;
}








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 mergeArray(left, sright);
}

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

  배열의 가운데를 나타내는 포인터를 만들고 그 포인터를 기준으로 slice메서드를 활용하여 2개의 배열로 분할 한 후, 그 분할 된 배열들을 재귀적으로 계속 분할하고 0개 또는 1개의 요소를 가질때 까지 계속 분할한다. 그리고 리턴 값으로 mergeArray함수를 호출하여 왼쪽 오른 쪽 배열을 정렬하여 합병하고 반환하고 반환하고 반환하여 마지막으로 left에 해당하는 범위의 요소들을 정렬시킨 배열을 할당하고, right에 해당하는 범위의 요소들을 정렬시킨 배열을 할당한다. 마지막으로 두 배열을 mergeArray함수를 통해 정렬한 후 반환하는 것이다.