Merge Sort

선결론 : Merge Sort는 최악의 시나리오에는 O(n log n)이지만 메모리를 너무 사용할 수도 있다는 점

 

 

오늘은 sorting 알고리즘 중 하나인 merge sort 에 관한 글을 써보고자 한다.

 

Merge Sort (???)

Merge Sort은 간단하게만 보자면 데이터를 정리할 때 사용되는 방법 중 하나이다. 데이터를 정리할 때 어떤 방법을 사용하느냐에 따라 매우 다른 효율성을 보여줄 수 있는데, merge sort 의 시간 복잡도는 최악의 경우에 O(log n)으로 나쁘지 않다고 판단이 되는 것 같다.

 

일단 간단한 소개는 역시 GIF가 최고라고 생각하기 때문에 아래에 우연히 찾아낸 이미지를 삽입했다.

https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-2.php

 

위 그림에서 보이는 것처럼 사실 작동하는 방식은 매우 단순하다.

- 주어진 배열을 각각 따로따로 될 때까지 분해하고

- 두 개씩 순서대로 합치고 정리한 뒤에

- 하나의 배열로 완성이 될 때까지 반복하면 된다.

 

이렇게 하면 되긴 하는데, 코드로 표현하지 않으면 뭔가 아쉽기도 하고,

내가 Javascript에서 시도했던 것들을 기록하고자 몇 개의 예시들을 보여주고자 한다.

 

 

---

 

Naive vs Natural

일단, naive merge sort 과 natural merge sort 라는 두 가지가 있다.

Naive 는 말 그대로 계속해서 쪼갠 뒤에 하나씩 될 때 다시 2 개씩 합치는 거다.

Natural 은 이어지는 것들을 이용해서 쪼갠 뒤에 다시 합치는 거다.

 

어떻게 보면 Natural이 조금 더 효율적일 수도 있다는 직관적인 결론이 나오기도 하지만 일단 코드를 보장

 

const mergeSort = array => {
	// 만약에 전달 받은 배열의 길이가 하나일 경우 (base case) 그 자체를 돌려준다
    if (array.length < 2) return array;
    
    // 아닌 경우, 이제부터 하나가 될 때까지 반으로 나누는 과정을 거친다
    
    const middleIndexOfArray = Math.floor(array.length / 2);
    
 	const leftArray = array.slice(0, middleIndexOfArray);
    const rightArray = array.slice(middleIndexOfArray);
    
    // 그냥 돌려주지 않고 재귀함수를 이용해 계속해서 나눠주는 과정이다
    return mergeArrays(mergeSort(leftArray), mergeSort(rightArray));
}

 

이렇게 위처럼 배열이 주어지면, 길이를 확인 후, 하나로 나눠질 떄까지 계속해서 반으로 나눌 것이다

다 나눈 뒤에는 이제 합쳐야 하니까 mergeArrays라는 함수를 만들어 이를 합쳐준다.

 

코드에 들어가기 앞서, 일단 합치는 과정을 GIF를 보면 알겠지만, 방식은 어느 정도 단순하다.

주어진 왼쪽과 오른쪽 배열들을 비교하는데, 이때 해야하는 가정은 배열 자체는 순서대로 되어 있다는 가정이다.

사실 이것은 하나씩  나눠줄 때 다시 합치는 과정을 이 함수가 해주기 때문에 여기서 나오는 결과를 가지고 다시 합치는 거랑 마찬가지라고 봐도 무관하다.

 

그럼 일단 코드를 한번 짜보자

 

const mergeArrays = (leftArray, rightArray) => {
	// 새롭게 반환할 배열을 생성한다
  	const mergedArray = [];

	// 일단 길이와 포인터를 가지고 접근을 하기 위해서 4가지 변수를 만들어준다
    // 길이는 숫자로 하여 비교가 빠르게 만들어준다
    const leftArrayLength = leftArray.length;
    const rightArrayLength = rightArray.length;
    
    let leftPointer = 0;
    let rightPointer = 0;
    
    while (leftPointer < leftArrayLength && rightPointer < rightArrayLength) {
    	// pointer들은 추가할 때 ++ 로 계속해서 증가시켜준다
    	if (leftArray[leftPointer] < rightArray[rightPointer]) {
        	// 왼쪽 배열의 항목보다 오른쪽 배열의 항목이 클 때, 작은 것을 넣어야 한
            mergedArray.push(leftArray[leftPointer++]);
        } else {
        	// 왼쪽 배열의 항목이 오른쪽 배열의 항목보다 크거나 같을 때
            // 같으면 어느 것을 넣는지 상관이 없다는 것 유의
            mergedArray.push(rightArray[rightPointer++]);
        }
    }
	return mergedArray.concat(
            leftArray.slice(leftPointer)
    	    .concat(rightArray.slice(rightPointer))
        );
}

 

코드가 딱히 어렵지가 않아 바로 이해가 될 것이라고 생각이 된다.

 

보면 알겠지만 바로바로 비교 후에 넣어주고 마지막에는 두 개의 배열 중 하나라도 길이 이상이 되어 버리면 즉각 멈추고 남은 항목들을 배열에 concat 해주는 식이다. 이렇게 급 마무리 해도 되냐고 의문이 들 수가 있고 어떻게 확인을 안 해도 되는지 궁금할 수도 있는데,

남은 배열들은 어떻게 보면 mergedArray에 들어간 마지막 항목보다 최소한 그 이상으로 큰 항목들이다.

 

그렇기 때문에 이러한 항목들을 두고 있는 배열의 항목들은 전부 다 마지막 항목보다 크다는 결론이 도출되고

여기서 순서와 상관 없이 다 합쳐주면 완성이 된다.

 

 

---

 

Natural Merge Sort으로 한다면...???

여기서 만약에 위에서 말했던 방식처럼, 굳이 하나씩 나누지 않고 일단 왼쪽 오른쪽으로 나누는 건 동일한데 이어지는 첫번째 배열과 나머지 배열로 나누면 어떨까라고 생각을 해봐서 진행했다.

 

내가 짜봤던 코드는 

 

const mergeSort = array => {
  // Need to find the first breakpoint where the prev value is bigger than next value
  let breakPoint;
  for (let i = 1; i < array.length; i += 1) {
    if (array[i - 1] < array[i]) {
      continue;
    } else {
      breakPoint = i;
      break;
    }
  }

  if (breakPoint) {
    const leftArray = array.slice(0, breakPoint);
    const rightArray = array.slice(breakPoint);
    return mergeArrays(leftArray, mergeSort(rightArray));
  }

  return array;
};

 

위와 같은데, 이 때 발생하는 문제가 heap이 넘친다는 것이다. 그렇다.... 주르르륵....

javascript는 이미 high-level language인데 거기서 더 효율을 낮춰버리니 모든 것이 죽어버리는...

 

아무튼 이런 암담한 결과는 다른 생각으로 번졌다. 

만약에 breakpoint, 즉 이어지는 배열을 나누는 지점이 두 개 이상이면 그냥 반으로 나누고 아니면 breakpoint 로 나누면 어떨까라는 생각이 들었다.

 

그래서 작성해봤던 코드는 아래와 같다.

const mergeSort = array => {
  // Create a flag
  let splitHalf = false;
  let breakPoint;

  for (let i = 1; i < array.length; i += 1) {
    if (array[i - 1] < array[i]) {
      continue;
    } else {
      if (splitHalf) {
        break;
      }
      splitHalf = true;
      breakPoint = i;
    }
  }

  if (splitHalf) {
    const middleIdx = Math.floor(array.length / 2);
    const leftArray = array.slice(0, middleIdx);
    const rightArray = array.slice(middleIdx);
    return mergeArrays(mergeSort(leftArray), mergeSort(rightArray));
  } else {
    if (breakPoint) {
      const leftArray = array.slice(0, breakPoint);
      const rightArray = array.slice(breakPoint);
      return mergedArrays(leftArray, rightArray);
    } else {
      return array;
    }
  }
};

 

(갈수록 코드가 더러워지고 지저분해지는 것은 기분탓!)

 

이렇게 진행해 본 결과, 딱히 문제는 없었다...???

 

참고로 문제가 있다 없다의 기준은 0 부터 1000000 중 랜덤 숫자를 1000000 번 넣은 배열을 3초 이내에 정리하는 기준이다

 

그런데... 딱히 엄청나게 성능이 뛰어나졌다라고 말할 수가 없을만큼 기대를 무너뜨려버렸다... 역시 코드 너란 놈은...

 

잠시 쉬어가고자 밈을 넣어봤다 (ㅎㅎㅎ)

 

 

ㅜ쿠쿠쿠쿠쿠쿠

 

다음으로 시도해본 건 모든 것을 breakpoint로 나누는 작업이었는데...

이건... 크ㅡㅡㅇ흐브.. 실패작이지만...

 

실패는 성공의 어머니이시기 때문에 예의를 표하기 위해 넣었다

 

const mergeSort = array => {
  if (array.length < 2) return array;
  const breakpoints = getbreakpoints(array);
  debugger;
  return splitArrayByBreakPoint(array, breakpoints);
};

// Splitting arrays by breakpoints
const splitArrayByBreakPoint = (array, breakpoints) => {
  debugger;
  if (breakpoints.length < 2)
    return mergeArrays(
      array.slice(0, breakpoints[0]),
      array.slice(breakpoints[0])
    );

  const middleIdx = breakpoints[Math.floor(breakpoints.length / 2)];
  const leftArray = array.slice(0, middleIdx);
  const rightArray = array.slice(middleIdx);

  const newLeftbreakpoints = breakpoints.slice(
    0,
    breakpoints.indexOf(middleIdx)
  );
  const newRightbreakpoints = breakpoints
    .slice(breakpoints.indexOf(middleIdx))
    .map(point => point - middleIdx);
  debugger;

  return mergeArrays(
    splitArrayByBreakPoint(leftArray, newLeftbreakpoints),
    splitArrayByBreakPoint(rightArray, newRightbreakpoints)
  );
};

// Going to store breakpoints in an array
const getbreakpoints = array => {
  let breakpoints = [];

  for (let i = 1; i < array.length; i += 1) {
    debugger;

    if (array[i - 1] > array[i]) {
      breakpoints.push(i);
    }
  }
  debugger;

  return breakpoints;
};

 

(가장 더러운 코드)

 

아직까지 내가 작성한 것을 보고 이해가 안 가는 건 둘째치고 하려던 의도를 일단 설명하고자 글을 이어본다.

 

그러니까... 음... 일단 breakpoint들을 다 찾은 뒤에...

 

breakpoint를 기준으로 배열을 나눠서 다시 mergeArrays 함수를 불러오는 과정이다.

뭐... 통과가 안 되었다는 것은 두 말할 것도 없지만... 재미는 있었다

 

아무튼, 이렇게 오늘은 해봤던 merge sort 과 관련된 글을 작성해 봤는데,

실패를 계속하는 것이 시도를 멈춰야 한다는 것은 아니라는 것을 명심하면 언젠가는 성공할 것이라고 스스로를 위로하며 글을 마친다.