[JavaSrcipt] 정렬알고리즘 (합병)

✅ Merge Sort

 

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다.

일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

 

❗ 병합 정렬 혹은 합병 정렬이라고 불리는 Merge Sort는 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 방법이다.

❗ 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

 

❗ 합병 정렬단계
분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

❗ 합병 정렬의 과정
- 추가적인 리스트가 필요하다.
- 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

 

 

 

 

❗ 2개의 정렬된 리스트를 합병(merge)하는 과정

- 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
- 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
- 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
- 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

 

 

✅ merge sort 과정

 

❗ merge sort알고리즘 특징

 

-단점

병합 정렬은 in place 알고리즘이 아니기 때문에 별도의 메모리 공간이 필요하다.

만약에 정렬할 데이터의 양이 많은 경우에는 그만큼 이동 횟수가 많아지므로 시간적인 낭비도 많아지게 된다.

 

-장점

병합 정렬은 최선의 경우에도, 최악의 경우에도 O(nlog₂n)의 시간이 소요되기 때문에 데이터 분포에 영향을 덜 받는다.

항상 동일한 시간이 소요되므로 어떤 경우에도 좋은 성능을 보장받을 수 있다.

 

function mergeSort (array) {
    if (array.length < 2) {
       return array;
    }
    const mid = Math.floor(array.length / 2);

    const left = array.slice(0, mid);
    const right = array.slice(mid);

    return merge(mergeSort(left), mergeSort(right));


    function merge (left, right) {
        const resultArray = [];
        let leftIndex = 0;
        let rightIndex = 0;
        
        while (leftIndex < left.length && rightIndex < right.length) {
          if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
          } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
          }
   	}
      
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
    }
}
console.log(mergeSort([5, 4, 3, 2, 1]));

 

먼저 array의 길이가 2보다 작으면 분할이 끝난 것이므로 array를 그대로 return한다.
만약 2보다 크다면 반으로 나눈다.

 

left와 right으로 나눠진 배열은 각각 merge라는 함수를 호출하여 병합한다.
merge함수는 최종으로 합쳐진 배열을 담을 resultArray라는 배열을 준비하고
두 배열의 앞자리 숫자부터 비교하여 배열에 담는다.
while문을 빠져나오면 두 배열 중 숫자가 작은 한 쪽 배열의 요소가 resultArray에 담기기 때문에
resultArray에 left와 right 배열을 다시 합치고 리턴한다.

 

✅ 분할, 정복 중간 결과들

 

 

function mergeSort (array) {
    if (array.length < 2) {
       return array;
    }
    const mid = Math.floor(array.length / 2);  //  5/2      2/2

    const left = array.slice(0, mid);   // 5 4          //  5
    const right = array.slice(mid);     // 3 2 1        //  4

    return merge(mergeSort(left), mergeSort(right));
                // ❗ [5, 4]           // [3, 2, 1] 을 넣고 mergeSort호출
                // ❗ length 2         // length 3 이므로 다시 반복
    
                // ❗ [5]              // [4] 를 넣고 mergeSort호출
                // ❗ length 1         // length 1 2보다작으므로 array반환
                // ❗ 즉 재귀의 기반조건에 다다름
                // ❗ mergeSort([5]),mergeSort([4]) 는 [5] [4] 반환 
                // ❗ 즉 merge(5, 4) 넣고 호출
    

    function merge (left, right) {  // left 5 right 4
        const resultArray = [];
        let leftIndex = 0;
        let rightIndex = 0;
        
                 // ❗ left.length = 1    right.length = 1
                 // ❗ leftIndex rightIndex 둘다 0이므로 조건 만족
        while (leftIndex < left.length && rightIndex < right.length) {
          if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
          } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
          }
          
            // ❗ left = [5] 인데 leftIndex=0이므로 5와 right[0] 4를 비교
            // ❗ 4가 더 작음 else로 가서 4를 resultArray 에 push  rightIndex++
            // ❗❗  조건불만족 탈출  resultArray = [4]
            // ❗ left = 5 leftIndex = 0   right = 4 rightIndex = 1
            
     }
        // ❗ resultArray = [4] .concat left.slice(0) = 5  ==> [4,5]
        // ❗ right.slice(1) = 없음
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
    }
    // ❗ merge(5, 4)의 결과는 [4,5]
}
console.log(mergeSort([5, 4, 3, 2, 1]));

 

 

✅ slice

slice() 메서드는 어떤 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다.

원본 배열은 바뀌지 않습니다. 추출한 요소를 포함한 새로운 배열을 반환.

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

console.log(animals.slice(1, 5));
// expected output: Array ["bison", "camel", "duck", "elephant"]

console.log(animals.slice(-2));
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// expected output: Array ["camel", "duck"]

arr.slice([begin[, end]])

매개변수 

begin

0을 시작으로 하는 추출 시작점에 대한 인덱스를 의미합니다.
음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출합니다.
begin이 undefined인 경우에는, 0번 인덱스부터 slice 합니다.
begin이 배열의 길이보다 큰 경우에는, 빈 배열을 반환합니다.

end

추출을 종료 할 0 기준 인덱스입니다. slice 는 end 인덱스를 제외하고 추출합니다.
예를 들어, slice(1,4)는 두번째 요소부터 네번째 요소까지 (1, 2 및 3을 인덱스로 하는 요소) 추출합니다.
음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. 예를들어 slice(2,-1) 는 세번째부터 끝에서 두번째 요소까지 추출합니다.
end가 생략되면 slice()는 배열의 끝까지(arr.length) 추출합니다.
만약 end 값이 배열의 길이보다 크다면, silce()는 배열의 끝까지(arr.length) 추출합니다.

 

✅ concat

concat() 메서드는 인자로 주어진 배열이나 값들을 기존 배열에 합쳐서 새 배열을 반환합니다. 
기존배열을 변경하지 않습니다. 추가된 새로운 배열을 반환합니다.

const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2);

console.log(array3);
// expected output: Array ["a", "b", "c", "d", "e", "f"]

 

 

 

-출처

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://im-developer.tistory.com/134

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/slice

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/concat