퀵 정렬(Quick Sort)의 특징

• 가장 많이 사용되고 있는 빠른 정렬 알고리즘 중의 하나
• 큰 배열 하나를 정렬하는 것 보다는 작은 배열 여러 개를 정렬하는 것이 빠르다는 것을 이용
• 비교 기반 정렬 알고리즘
• 분할 정복(divide and conquer) 방식 알고리즘
• 안정적이지 않은 정렬(동일한 키 값이 있을 경우 순서가 바뀔 수 있음)
• 최악 O(n^2), 평균 O(n log n)
• 주어진 데이터들이 이미 정렬되어있는 경우 최악의 수행시간을 보임

알고리즘

1. 정렬할 리스트 중에서 하나의 원소를 선택한다. 이 원소를 피벗(Pivot)이라고 한다.
2. 피벗의 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 큰 값들이 오도록 만든다.
3. 피벗 기준 왼쪽 배열과 오른쪽 배열에 다시 피벗을 각각 선정한 뒤 재귀적으로 퀵 정렬을 수행한다.

최적의 피벗(Pivot)

퀵 정렬의 핵심은 피벗 값의 설정이다.

피벗을 어떻게 선택하냐에 따라서 알고리즘의 성능이 큰 편차를 보인다.

• 최악 : 이미 정렬되어있는 리스트에서 매번 첫 번째 원소를 피벗으로 고를 때. O(n^2)의 수행시간을 보인다.
• 최적 : 매번 자료의 중위값(median)을 피벗으로 고를 때. O(n log n)의 수행시간을 보인다.

하지만, 정렬되지 않은 리스트에서 중위값을 선택해야하는 문제에 봉착하게 된다.

좋은 피벗 값을 찾기 위한 방법은 여러 가지가 있지만 몇 가지만 살펴보면,

• random pivot : 난수를 발생시켜 피벗을 랜덤하게 뽑음
• midean of three : 랜덤 인덱스를 3개를 뽑은 뒤, 이 3개의 중위값을 피벗으로 사용

등의 방법이 있다.

구현

const quickSort = (list) => {
    let lte = []; // 피벗보다 작은 원소들을 담을 배열
    let gte = []; // 피벗보다 큰 원소들을 담을 배열
    let pivot = list[0]; // 배열의 첫 번째 원소를 피벗으로 하기로 하자

    /*
        루프를 돌면서 피벗보다 작은 원소는 lte에, 피벗보다 큰 원소는 gte에 담은 다음,
        [ lte ] - [ pivot ] - [ gte ] 이렇게 배열을 이어붙히는 과정을 재귀호출
    */
}

class Quicksort {
    constructor(_list) {
        const list = _list;
        const quicksort = list => {
            if (Array.isArray(list)) {
                if (list.length === 0) {
                    return [];
                }
                const lt = [];
                const gt = [];
                const pivot = list[0];
                for (let i = 0; i < list.length; i++) {
                    if (list[i] < pivot) {
                        lt.push(list[i]);
                    } else if (list[i] > pivot) {
                        gt.push(list[i]);
                    }
                }
                return quicksort(lt).concat(pivot, quicksort(gt));
            }
        };
        return quicksort(list);
    }
}

//-----------------------------------------------------

const data = [18, 15, 23, 28, 52, 59, 13];

const sortedData = new Quicksort(data); 

console.log(sortedData); // [ 13, 15, 18, 23, 28, 52, 59 ]