[110일차]병합정렬 알고리즘(merge-sort)

병합정렬 알고리즘

합병정렬은 맨해튼 프로젝트에 참여했던 폰노이만이 제안한 방법이다.

시간복잡도를 최악의경우에도 O(n log n)만큼 줄이는 방법인데,
기존 정렬알고리즘보다 확연히 줄어든다.
또 간단하다

합병정렬에는 크게 두가지 역할을 수행해야된다.

1. 좌 우를 기준으로 재귀적으로 나누기
2. 좌 우에다가 정렬된 두 배열을 합치는 함수 적용하기

나는 이 원리가 이해됐지만 처음 배웠을 땐 도저히 배열의 길이가 짝수일 때는 어떻게 해? 라는 의문을 풀어낼 수 없었다.
그래서 썼던 방법이 있는데 그림이나 종이로 숫자카드를 그리고 정렬 해보기였다.

---

1. 좌 우를 기준으로 재귀적으로 나누기

아래와 같은 배열이 있다.

이걸 딱 반틈만큼 잘라줘야 하는데,
배열의길이가 보다시피 홀수이다.
나누기 2를하면 4.5이고 뒤에 소수점을 땐 것만큼 잘라주자.

이렇게 지속적으로 나눈다면,
원소가 하나밖에 없어서 left Right를 안가지는 경우 가 있을건데,
그럴때는 그냥 그 값 자체를 놔두자.

재귀적으로 좌우 나눴다면 위와 같은 형태가 된다.

---

2. 오름차순으로 정렬된 두 배열을 비교하고 합치는 함수

오름차순으로 정렬된 두 배열을 합치는것이다.
결코 아무배열이나 합쳐지는것이 아님을 명심하자!

위와 같이 오름차순으로 정렬된 두 배열을
크기를 비교해가며 결과배열에 푸쉬해줄거다.

둘다 배열의 길이가 0이 아닐동안

각 배열의 0번째 인덱스를 비교한다.

더 작은 값을 꺼내서 결과에 푸쉬한다

각 배열의 0번째 인덱스를 비교한다.

더 작은 값을 꺼내서 결과에 푸쉬한다

한쪽배열의 길이가 0이 됐으므로 벗어난다.

길이가 0이 아닌 배열의 길이가 0이될때동안

배열의 맨 앞부분을 꺼내서 결과배열에 푸쉬한다

---

두 기능을 알아보았으니 수도코드를 어떻게 짤지 생각을 해보자

좌 우를 바로 비교하고 병합하는 함수를 적용하면 어떻게 될까?
오름차순으로 정렬되지 않았기에,
순서가 마음대로 섞일것이다.

그래서 한조각 한조각부터 정렬된 배열을 만들어주는거다

이 작은 한조각부터 합쳐간 값 을 최종적으로 리턴한다!

---

자바스크립트 코드

// 오름차순 된 배열을 합쳐주는 함수
function merge (arr1, arr2){
  // 결과배열을 선언한다.
  // 두 배열모두 길이가 0이 아닐동안  
    // 각배열의 0번째 인덱스를 비교한다.  
    // 더 작은값을 *꺼내서 (shift해야됨) 결과배열에 푸쉬한다.  
  
  // arr1의 길이가 0이 아닐동안  
    // 각 배열의 0번째 인덱스를 꺼내서 결과배열에 푸쉬한다.
 
  // arr2의 길이가 0이 아닐동안
    // 마찬가지로 각 배열의 0번째 인덱스를 꺼내서 결과배열에 푸쉬한다.
  
  // 합쳐진 결과배열을 리턴한다.  
 
  const result = [];
  while(arr1.length && arr2.length){
    if(arr1[0] < arr2[0]){
      result.push(arr1.shift())
    }else{
      result.push(arr2.shift())
    }
  }
 
  while(arr1.length){
    result.push(arr1.shift())
  }
 
  while(arr2.length){
    result.push(arr2.shift())
  }
 
  return result;
}
 
//test
console.log(merge([1, 3, 4], [2, 5, 9]))
 
function mergeSort (arr){
  // 만약 배열의 길이가 1이면 배열을 리턴한다.
  if(arr.length === 1)return arr;
  // 배열을 두동강 내서 좌 우로 구분시킨다.  
  const standard = parseInt(arr.length / 2);
  const left = arr.slice(0, standard);
  const right = arr.slice(standard);
  // 좌 우 각각 mergeSort시키고 merge한 값을 리턴한다.
  return merge(mergeSort(left), mergeSort(right));
}
 
//test
console.log(mergeSort([5, 9, 4, 1, 6, 3, 2, 8, 7]))

OUTPUT