Quick Sort ( JS )

Quick Sort

사전지식
1. pivot
2. partitioning

const arr =[9, 5, 2, 3, 7, 8, 4];
pivot을 5로 설정했을 때,
9 > 5 => 오른쪽
2 < 5 => 왼쪽
3 < 5 => 왼쪽
7 > 5 => 오른쪽
8 > 5 => 오른쪽
4 < 5 => 왼쪽
5 고정 이후 왼쪽 오른쪽에 또다시 pivot 설정하고 반복 동작
basic : pivot을 정해주고 나머지 elements를 partitioning

# 메모리 배열 안에서의 quick sorting 
const arr = [9, 5, 2, 3, 7, 8, 4];
같은 arr안에서 quick sorting을 하기 위해서
pivot 값인 5를 배열의 가장 끝의 원소와 교환
arr = [9, 4, 2, 3, 7, 8, 5];
이후 partitioning 동작
주황색 포인터 => pivot보다 값이 작아야하고,
분홍색 포인터 => pivot보다 값이 커야함
해당 조건을 만족하지 않으면 => Swap이 필요.
반복 작동하면서 주황색 포인터와 분홍색 포인터가 역전되는 경우에 pivot보다 큰 파티션에서 가장 왼쪽에 있는 숫자를 pivot과 교환
반복 수행

quick sort의 다양한 variation
1. pivot 설정 방식
2. 포인터 시작점 설정 방식

Complexity
Worst : O(n) = O(n^2); ## pivot이 최대,최소인경우
Avg/Best : O(n) = O(nlogn); ## pivot이 정확하게 중간값인 경우
단점
Unstable Sorting
코드 예시

function quickSort(nums, left, right) {
if(left<right){
// partition => 재정렬하는 함수
let pivot = partition(nums,left,right);
quickSort(nums,left,pivot-1);
quickSort(nums,pivot+1,right);
}
}