퀵정렬

y0ung·2020년 12월 23일
0

알고리즘개념

목록 보기
4/7

분할 정복 _ divid-and-conquer

재귀적 기술중 하나 이다.

분할 정복 젼략

  1. 가장 간단한 경우로 기본 단계를 찾는다.
  2. 주어진 문제를 작게 줄여서 기본단계가 되도록 만드는 법을 찾아낸다.

퀵 정렬 _ quicksort

선택 정렬보다 빠르고 실제로 자주 사용된다.

  1. 기준 원소를 고른다(배열에서 고른 원소 하나)
  2. 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 두개의 하위 배열로 분할 한다.
  3. 하위 배열에 대해 재귀 적으로 퀵 정렬을 호출한다.
function quicksort(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    let pivot = arr[0]; // 재귀단계 (10 -> 기준 원소)

    let less = [];
    let greater = [];

    for (let i of arr) {
      if (i < pivot) {
        less.push(i); // 기준원소보다 작은 원소로 이루어진 배열
      } else if (i > pivot) {
        greater.push(i); // 기준 원소보다 큰 원소로 이루어진 배열
      }
    }

    return [...quicksort(less), pivot, ...quicksort(greater)];
  }
}

console.log(quicksort([10, 5, 2, 3]));

spread(...) 연산자를 사용하지 않고 사용할수 있는 방법이 무엇일까..?

TIP

귀납적 증명
위의 코드는 귀납적 증명을 적용한 코드인데, 귀납적 증명은 알고리즘이 제대로 동작하는지 증명하는 방법중 하나이다.

귀납적 증명에도 기본단계와 귀납 단계 두가지 단계가 필요하다.

요약

  • 분할 정복은 문제를 더 작은 조각으로 나누어 푼다. 만약 리스트에 분할 정복을 적용한다면 기본 단계는 원소가 없는 빈 배열이거나 하나의 원소만 가진 배열이 된다.

  • 퀵 져ㅓㄹ렬을 구현하려면 기준 우너소를 무작위로 선택 한다. 퀵 정렬의 평균적인 실행 시간은 O(n log n)이다.

  • 단순 탐색과 이진 탐색을 비교할 때는 상수항이 전혀 문제가 되지 않는다. 리스트가 길어지면 O(log n)O(n)보다 빨라지기 때문이다.


참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.

profile
어제보다는 오늘 더 나은

0개의 댓글