[javascript] Merge Sort !

포스팅 전 주저리 : 매직마우스2를 오래 사용하다 손목터널증후군 때문에 손모가지 날라갈뻔하다 결국 커세어 m65 Pro RGB로 바꾼지 1주일 되가는데 손목이 너무 편하다. 몇일전까지만 해도 핸드폰만 들고 있어도 손목에 통증이 느껴졌는데, 대 만족이다. 

 

Merge Sort란 

병합정렬이라고도 불리는 합병정렬은 존 폰 노이만에 의해서 개발했다. 이 합병정렬은 Quicksort가 최악의 경우 (n2)의 시간 복잡도를 가지는데 반해, 최악의 경우에도 O(n log n)의 시간 복잡도를 가지는 안정정렬이다.

 

알고리즘

1. 인자로 넘겨 받은 배열을 배열의 길이가 1이 될 때 까지 반으로 쪼갠다.   (분할)

 

2. 왼쪽과 오른쪽으로 나누어진 배열의 원소를 비교한 후 큰 수를 오른쪽으로 보내어 새로운 array를 만든다. (합병)

 

3. 새롭게 병합된 배열둘의 아이템을 비교해서 새로운 배열을 만들어 낸다. (합병)

 

Merge Sort가 일어날 때 내부

 

중요한 부분은 합병이 일어날때이다. 왼쪽 배열과 오른쪽 배열의 원소를 비교하여 왼쪽 배열[0]과 오른쪽 배열[0]을 비교하여 작은 수를 새로운 배열[0]에 넣는다. 그 후 이동한 아이템이 있는 배열에 있는 남은 배열의 아이템과 다른 배열의 아이템을 비교하여 다시 새로운 배열에 작은 수를 넣는다. 왼쪽, 오른쪽 배열의 아이템이 전부 새로운 배열로 옮기기 전까지 반복한다. 

 

Merge Sort 예제 

필요한 함수 : Merge , ,MergeSort

 

function Merge(left,right){
   let leftIndex = 0;
   let rightIndex = 0;
   let leftLength = left.length;
   let rightLength = right.length;
   let array = [];
   do{
       if(left[leftIndex] <= right[rightIndex]){
           array.push(left[leftIndex]);
           leftIndex++;
       }else if(left[leftIndex] >= right[rightIndex]){
            array.push(right[rightIndex]);
            rightIndex++;
       }
       console.log(leftIndex , leftLength)
   }while(leftIndex < leftLength && rightIndex < rightLength);
   // do while문을 작성 한 이유는 받은 배열의 길이가 1일때도 작동되게 하기 위해서이다.

   while(leftIndex != leftLength){
       array.push(left[leftIndex]);
       leftIndex++;
   }
	// 왼쪽 배열 있는거 털어주기
   while(rightIndex != rightLength){
       array.push(right[rightIndex]);
       rightIndex++;
   }
	// 오른쪽 배열 있는거 털어주기
   return array;
    
}

function MergeSort(array){
    if(array.length < 2) return array;
    let middle = Math.floor(array.length/2);
    let left = array.slice(0,middle); //첫번째 인자 기준으로 두번째 인자까지 배열을 잘라서 return
    let right = array.slice(middle);
    return Merge(MergeSort(left),MergeSort(right));
}

let array = [1,8,5,2,4,6,9,7,6];

console.log(MergeSort(array));

 

정리하며

 

개인적으로 퀵소팅 보다 훨씬 보기 좋고 쉬운 듯 하다. 아마 주로 쓰게될 정렬방법이 아닐까 싶다. 

 

참고 

https://www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4

(Algorithm) 합병(머지, 병합) 정렬

https://zeddios.tistory.com/38

합병정렬(Merge Sort) 알고리즘 정리 ( 개념 / 시간복잡도 - O(nlogn) )

MergeSort하는동안 변하는 내용을 하나하나 추적해서 보고싶으면 바로위 제디오스님의 사이트를 방문하기 바란다. 아마 파워포인트로 예제를 그림으로 만드신 모양인데 저 노가다를 일일히 다 하시다니 그 노고에 감사를 표한다.