200125(토) : Merge Sort, Quick Sort

Bubble Sort와 Insertion Sort를 정리한 지난 글(link)에 이어 본 글에서는 Merge Sort와 Quick Sort를 정리한다.

 

1. Merge Sort

1) Merge Sort의 특징

Merge Sort와 Quick Sort는 기본적으로 'DIVIDE AND CONQUER' 알고리즘과 'RECURSION'이 사용된다. Bubble과 Insertion은 모든 요소를 한 번 이상씩 방문하며 반복문 안에 반복문이 중첩되는 형태이기 때문에 시간복잡도에서 O(n^2)를 피할 수 없었다. 하지만 'DIVIDE AND CONQUER'를 하는 순간 방문해야 하는 element의 수가 절반으로 줄어들기 때문에 훨씬 효율적인 알고리즘이 된다.

 

[Big O]

• Best Case : O(n log n)
• Worst Case : O(n log n)
• 공간복잡도 : O(n)

추후 알아볼 Quick Sort와 달리, Merge Sort의 시간복잡도는 항상 O(n log n)이다. 하지만 추가적인 공간을 할당하여 정렬된 값들을 넣어야하기 때문에 공간복잡도가 O(n)이 된다는 단점이 있다.

 

[장점]

• O(n log n) : 언제나 O(n log n)이 보장되므로 O(n^2)보다 훨씬 효율적이다.
• 'STABLE' : 정렬 과정에서 원본의 순서가 보장된다.

[단점]

• 공간복잡도가 O(n) : 추가적인 공간을 할당할 수 밖에 없기 때문에 메모리를 잡아먹는다.

merge sort

 

2) Merge Sort의 로직

1) 전체 배열을 반으로 나눈다.
2) 모든 element가 길이가 1이 될 때까지 재귀를 통해 계속 반으로 자른다.(DIVIDE)
3) 분할이 완료되면, 두 요소를 비교하면서 작은 값이 앞으로, 큰 값이 뒤로 오도록하여 병합(MERGE)한다.

 

대략적인 흐름은 저러하나 이해가 어려울 수 있으니 코드로 확인해보자.

 

3) Merge Sort 구현

const unsortedData = [-10, 3, 6, 2, 0, 28, -19, 25];

function mergeSort (arr) {
  if (arr.length === 1) return arr;

  const length = arr.length;
  const mid = Math.floor(length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

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

function merge (left, right) {
  const result = [];
  let leftIdx = 0;
  let rightIdx = 0;

  while (leftIdx < left.length && rightIdx < right.length) {
    if (left[leftIdx] < right[rightIdx]) {
      result.push(left[leftIdx]);
      leftIdx++;
    } else {
      result.push(right[rightIdx]);
      rightIdx++;
    }
  }

  return result.concat(left.slice(leftIdx)).concat(right.slice(rightIdx));
}

mergeSort(unsortedData);

 

2. Quick Sort

1) Quick Sort의 특징

Quick Sort는 Merge Sort와 마찬가지로 기본적으로 'DIVIDE AND CONQUER'와 'RECURSION'을 사용한다. 더불어 Quick Sort는 pivot이라는 개념을 활용한다. pivot을 정하고, pivot보다 작은 수는 왼쪽으로, pivot보다 큰 수는 오른쪽으로 위치시키고, 이후 좌 우 각각에 대해서 위의 과정을 재귀로 반복하는 형태이다.

 

[Big O]

• Best Case : O(n log n)
• Worst Case : O(n^2) - 이미 정렬이 되어 있는데 가장 작은 수 혹은 가장 큰 수를 pivot으로 고르게 될 경우, 사실상 divide가 이뤄지지 않기 때문에 O(n^2)이 된다.
• 공간복잡도 : O(log n)

 

[장점]

• O(n log n) : 빠르다.
• 'IN PLACE'

 

[단점]

• 'UNSTABLE' : 정렬 과정에서 원본의 순서가 변동될 수 있다.
• pivot : pivot 선정에 따라서 성능이 좌우된다.
• 이미 정렬된 데이터를 대상으로는 좋지 않다.

 

2) Quick Sort의 로직

1) pivot을 정한다.
2) pivot을 기준으로 왼쪽 index의 원소가 pivot의 값보다 작으면 왼쪽의 index를 1씩 더해준다.
3) pivot을 기준으로 오른쪽 index의 원소가 pivot의 값보다 크면 오른쪽의 index를 1씩 빼준다.
4) 2), 3)의 과정을 거치면 pivot의 왼쪽에서는 pivot보다 큰 수를 찾고, pivot의 오른쪽에서는 pivot보다 작은 수를 찾게된다.
5) 이 때 왼쪽 원소와 오른쪽 원소의 위치를 서로 변경시켜준다.
6) 이후 왼쪽 index와 오른쪽 index가 서로 만나면 해당 위치로 pivot을 이동시킨다.
7) pivot이 이동된 이후 왼쪽과 오른쪽의 data를 대상으로 각각 1)~6)번의 과정을 재귀로 돌려 정렬시킨다.

 

3) Quick Sort 구현

const unsortedData = [-10, 3, 6, 2, 0, 28, -19, 25];

function partition (arr, left, right, pivotIdx) {
  let temp;
  let pivot = arr[pivotIdx];

  while (left <= right) {
    while (arr[left] < pivot) left++;
    while (arr[right] > pivot) right--;

    if (left <= right) {
      temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }

  temp = arr[left];
  arr[left] = arr[pivotIdx];
  arr[pivotIdx] = temp;

  return left;
}

function quickSort (arr, left, right) {
  if (!left) left = 0;
  if (!right) right = arr.length - 1;

  let pivotIdx = right;
  pivotIdx = partition(arr, left, right - 1, pivotIdx);

  if (left < pivotIdx - 1) quickSort(arr, left, pivotIdx - 1);
  if (pivotIdx + 1 < right) quickSort(arr, pivotIdx + 1, right);

  return arr;
}

quickSort(unsortedData);