분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다.

퀵정렬(Quick sort)

피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 알고리즘

퀵정렬도 병합정렬과 마찬가지로 분할정복을 통한 정렬방법이다. 병합정렬과의 차이점은 병합정렬은 분할 단계에서는 아무것도 하지않고 병합하는 단계에서 정렬을 수행하지만, 퀵정렬은 분할 단계에서 중요한 작업들을 수행하고 병합시에는 아무것도 하지않는다는 점이다.

순서

1. 입력된 자료 리스트에서 하나의 원소를 고른다. 이 원소를 피벗이라고 부른다.
2. 피벗을 기준으로 리스트를 둘로 분할한다.
3. 피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮긴다
4. 피벗을 기준으로 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮긴다

예제

function quickSort(arr, left, right) {
  if (left < right) {
    //기준점을 찾고 기준점을 중심으로 더 작은수, 더 큰수 분류
    const i =  position(arr, left, right);
    //기준점 기준 좌측 정렬
    quicksort(arr, left, i - 1);
    //기준점 기준 우측 정렬
    quicksort(arr, i + 1, right);
  }
  return arr;
}
function position (arr, left, right) {
  let i = left;
  let j = right;
  const pivot = arr[left];

  //제자리 더 큰수/더 작은 수 좌우 배치.
  while (i < j) {
    while (arr[j] > pivot) j--;
    while (i < j && arr[i] <= pivot) i++;

    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  arr[left] = arr[j];
  arr[j] = pivot;

  return j;
}

병합정렬(Merge sort)

반으로 나누고 나중에 합치면서 정렬하는 알고리즘

병합정렬은 일종의 분할 정복법 중 하나로 큰 문제를 작은 여러 개의 문제로 쪼개서 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 방법이다. 병합이라는 이름 그대로 주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘이다.

병합정렬은 항상 O(nlogn)의 시간복잡도를 가지기 때문에 효율적이다. 그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야하기 때문에O(n)의 공간복잡도를 가진다. 한마디로 메모리를 팔아 수행속도를 얻는 경우라고 할 수 있다.

순서

1. [5, 0, 4, 1]라는 자료를 받았다
2. length가 1이 될때까지 자료 리스트를 반으로 쪼갠다
3. [5, 0], [4, 1]가 된다.
4. [5], [0], [4], [1]가 된다
5. 각 리스트의 길이가 1이 되었으므로 병합을 시작한다
6. 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합. [5]와 [0] 중 0이 더 작으므로 새로운 리스트에 0을 먼저 병합한다
7. [0, 5] 생성
8. 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합. [4]와 [1] 중 1이 더 작으므로 새로운 리스트에 1을 먼저 병합
9. [1, 4] 생성
10. 이제 [0, 5]와 [1, 4]를 병합한다. 이 리스트들은 정렬되었기 때문에 작은 인덱스일 수록 작은 값을 가진다는 것이 보장되어있다.
11. 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
12. [0] 생성. [5]와 [1, 4]가 남았다
    왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
13. [0, 1] 생성. [5]와 [4]가 남았다
14. 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
15. [0, 1, 4] 생성. [5]가 남았다
16. 값이 남았으므로 그냥 병합해준다.
17. [0, 1, 4, 5] 정렬완료

예제

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

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

  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없다.
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
  
  //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  //차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left), mergeSort(right));
}

Reference

https://evan-moon.github.io/2018/10/13/sort-algorithm/#%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACmerge-sort