분할정복 방법

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 분할 정복 방법은 대개 재귀를 이용하여 구현한다.

1. 퀵 정렬(Quick Sort)

특징

• 분할정복 알고리즘
• 대부분의 내장 라이브러리에서 존재하는 정렬 함수는 퀵 정렬 알고리즘을 사용한다고 한다.
• 합병 정렬(merge sort)과의 차이점은 퀵 정렬은 리스트를 비균등하게 분할

❓️ pivot

• pivot을 맨 왼쪽, 맨 오른쪽, 가운데로 잡는 quick정렬 등 어디로 잡든 상관이 없음
• 이 pivot의 기준 선정에는 아무런 연산이 없음
• 정렬이 끝나면 pivot의 위치가 중간으로 스왑이 된다.(정렬이 끝난 상태)

예시코드

function quickSort(arr) {
  // 배열의 요소가 하나만 남으면 값을 반환 후 종료된다.
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0]; // 0번 인덱스를 기준(pivot)으로 둔다.
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left),pivot,...quickSort(right)];
  // return에서 다시 함수를 불러와 배열의 요소가 하나만 남을 때까지 돌린다.
}

⏱ 시간 복잡도

• pivot을 어디로 잡느냐에 따라 차이가 크다!
  최선의 경우 O(nlogn), 최악의 경우 O(n^2)
  평균은 pivot을 랜덤하게 선택할때이고, O(nlogn)

👍 장점

• 평균적으로 속도가 빠르다.
• 추가 메모리 공간이 필요하지 않다.
• 한번 결정된 pivot의 위치는 변하지 않기 때문에 효율적이다.

👎 단점

• 정렬된 데이터에서는 오히려 수행시간이 오래걸린다.

(ex) [1,2,3,4,5,6,7,8,9,10] 의 정렬된 배열이 있을 때,

1을 pivot으로 둔다면, 자신 보다 작은 값을 찾기 위해 10까지 탐색하지만 10까지가도 없으니까 다시 돌아와서 1만 정렬한다. 이것을 10번 반복하게 될 것이다. 그러면 O(n^2) 의 시간이 걸린다.

2. 병합 정렬(Merge Sort)

• 분할정복 알고리즘
• 배열을 왼쪽 절반, 오른쪽 절반으로 분할하며 최소 단위(길이가 0 or 1)로 쪼갠 후 정렬을 진행한다.(0 또는 1이면 이미 정렬된 것으로 본다.)
• 쪼갠 영역들(이미 정렬이 되어 있음)을 차례대로 두개씩 병합한다.

예시코드

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

  const mid = Math.floor(arr.length / 2); // Math.floor 내림 메서드
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  // 이 식들은 배열을 세 부분으로 나누어주는 역할

  return merge(mergeSort(left), mergeSort(right)); //배열의 크기가 1이하가 될때까지 계속 나눠줄 것이다.
} 

function merge(left, right) { // 배열 요소 크기를 비교한 후 정렬 및 병합 하는 함수
  let result = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) { // 배열 요소의 크기를 비교한 후 크기에 맞게 result 배열에 넣어준다.
      result.push(left.shift()); 
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift())
  }
  while (right.length) {
    result.push(right.shift())
  }

  return result;
}

⏱ 시간 복잡도

• 최선, 평균, 최악 모두 O(nlogn)

👍 장점

• 항상 일정한 시간 복잡도 O(nlogn).
• 동일한 값에 대해 기존의 순서가 유지되는 stable 정렬.

👎 단점

• 정렬을 하는 배열외의 추가적인 임시 배열(추가적인 메모리)이 필요.
• 정렬하고자 하는 배열의 크기만큼의 추가적인 크기가 요구된다.

3. 힙 정렬(Heap Sort)

• 최대 힙 트리나 최소 힙 트리를 구성하여 정렬하는 방식(즉, 부모의 값이 자식의 값보다 항상 크거나 항상 작다)
• 내림차순 정렬을 위해서는 최대 힙 트리를 구성하고 오름차순 정렬을 위해서는 최소 힙 트리를 구성하여 정렬을 하는 방법

✅️ 용어정리

• 힙(Heap): 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조,
  힙은 배열을 사용해 표현한 트리와 같은 자료 구조라고 할 수 있음

• 우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조로 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

• 완전 이진 트리: 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

• 최대 힙 트리: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

• 최소 힙 트리: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  

힙 정렬(heap sort) 알고리즘의 개념 요약

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

• 과정 설명

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
   • 내림차순을 기준으로 정렬
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
3. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

⏱ 시간 복잡도

• 최선, 평균, 최악 모두 O(nlogn)

👍 장점

• 가장 크거나 가장 작은 값을 구할 때 유용하다. → 한번의 힙 구성을 통해 구하는 것이 가능하다.
• 멀리 떨어진 요소들을 정렬할 때 유용하다 → 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다.
• 항상 같은 시간 복잡도를 가지기 때문에 성능이 준수하다.

👎 단점

• 같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교하면 느린 편
• 퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다.

참고

VISUALGO