재귀적 기술중 하나 이다.
분할 정복 젼략
1. 가장 간단한 경우로 기본 단계를 찾는다.
2. 주어진 문제를 작게 줄여서 기본단계가 되도록 만드는 법을 찾아낸다.
선택 정렬보다 빠르고 실제로 자주 사용된다.
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 알고리즘' 책을 공부하여 요약정리한 내용입니다.