[Sort] Quick Sort

Quick Sort

---

pivot이라는 기준점을 잡은 뒤, 요소가 이 pivot보다 작다면 왼쪽, 크다면 오른쪽으로 자리를 이동시킨다.
문제를 작은 2개의 문제로 분리한 후, 해결하고 다시 합치는 분할 정복 방법을 사용한다.
시간복잡도는 O(nlog(n))

 

구현한 코드

function quick(array) {
    // 임의로 배열의 맨 끝 요소를 pivot으로 설정하고
    // pivot을 기준으로 왼쪽 / 오른쪽으로 나누기
    // pivot보다 작다면 왼쪽 배열에 / 크다면 오른쪽 배열에 넣기
    // 정렬된 배열을 왼쪽, pivot, 오른쪽 순서대로 합쳐서 리턴

    if(array.length < 2) {
        return array;
    }

    const pivot = array[array.length-1];
    let left = [];
    let right = [];

    for(let i = 0; i < array.length-1; i++) {
        if(array[i] < pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }

    return [...quick(left), pivot, ...quick(right)];
}