퀵 정렬(Quick Sort)

특징

• 이름 그대로 빠른 정렬
• 배열을 피벗(Pivot) 기준으로 두 개의 리스트로 나눕니다. 하나는 피벗보다 작은 값들의 리스트, 나머지 하나는 피벗보다 큰 값들의 리스트입니다(일반적으로 피벗 왼쪽으로 작은 값, 오른쪽으로 큰 값들의 리스트가 옵니다). 이렇게 배열을 나누는 것을 분할(Divide)라고 합니다. 나뉘어진 리스트들에 대해 위 과정을 재귀적으로 수행합니다.
• 재귀 호출이 한 번 수행될 때마다 최소 하나의 원소는 위치가 정해지기 때문에 알고리즘이 언젠가는 끝난다는 것을 보장할 수 있습니다.
• 분할 정복(Divide and Conquer) 알고리즘을 기반으로 정렬되는 방식입니다.
• 데이터를 비교하며 정렬하기 때문에 비교 정렬입니다.
• 정렬 대상 외 추가 공간이 필요하지 않습니다.

정렬 과정

1. 피벗을 하나 선택합니다.(현재 배열의 가장 왼쪽, 중간, 마지막 원소를 선택하는 세 가지 방식이 대표적입니다)
2. 피벗을 기준으로 왼쪽부터 피벗보다 큰 값을, 오른쪽에서부터 피벗보다 작은 값을 찾습니다.
3. 찾은 두 원소를 교환합니다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2, 3번 과정을 반복합니다.
5. 엇갈린 지점이 나오면 피벗보다 작은 원소를 피벗과 교환합니다.
6. 교환된 피벗 기준으로 두 개의 부분리스트로 나누어 1번 과정부터 진행합니다.
7. 나누어진 부분리스트 길이가 1이 아닐 때까지 위 과정을 반복합니다.
8. 인접한 부분리스트끼리 합칩니다.

효율

• 시간복잡도
  
  • 평균적인 경우: O(Nlog₂N)
  • 최악의 경우: O(N²)
    • 이미 정렬된 배열의 경우 왼쪽 피벗과 오른쪽 피벗은 부분리스트의 크기가 한쪽으로 쏠리게 되어 분할 정복의 이점을 살릴 수 없습니다(N번 분할 * N번 비교).
    • 다만, 중간 피벗의 경우에는 상대적으로 균등하게 부분리스트를 나눌 수 있으므로 비교적 성능을 끌어올릴 수 있습니다. 다만 중간 피벗을 선택한다고 하더라도 삽입 정렬보다는 성능이 떨어집니다.
• 공간복잡도: O(N)
  • 주어진 배열 안에서 교환으로 정렬됨

구현

왼쪽 피벗

let quickSort = function (start, end) {
    if (start >= end) { // 길이가 1인 경우 종료
        return;
    }
    let pivot = sample[start]; // 왼쪽 피벗
    let i = start + 1; // 왼쪽 탐색 인덱스
    let j = end; // 오른쪽 탐색 인덱스
    while (i <= j) { // 두 탐색 인덱스가 엇갈릴 때까지 반복
        // 피벗보다 큰 값 나올 떄까지 오른쪽으로 탐색
        while (i <= end && sample[i] <= pivot) { // 피벗과 비교할 원소를 참조할 수 있는 인덱스 범위를 지정해줘야함
            i++;
        }
        // 피벗보다 작은 값 나올 때까지 왼쪽으로 탐색
        while (sample[j] >= pivot && j > start) { // 엇갈린 후 피벗과 교체하려면 start보다 커야함
            j--;
        }
        if (i > j) { // 엇갈리면 피벗과 작은 값을 교체
            sample[start] = sample[j];
            sample[j] = pivot;
        } else { // 엇갈리지 않았다면 두 값을 교체
            let temp = sample[i];
            sample[i] = sample[j];
            sample[j] = temp;
        }
    }
    console.log(...sample);
    // 엇갈려서 빠져나오는 경우, 교체된 피벗 위치를 기준으로 나눠 각각 퀵정렬 수행
    quickSort(start, j - 1);
    quickSort(j + 1, end);
}

let sample = [7, 3, 2, 8, 9, 4, 6, 1, 5];
quickSort(0, sample.length - 1);

/* 정렬 과정 출력
6 3 2 5 1 4 7 9 8
4 3 2 5 1 6 7 9 8
1 3 2 4 5 6 7 9 8
1 3 2 4 5 6 7 9 8
1 2 3 4 5 6 7 9 8
1 2 3 4 5 6 7 8 9
*/