[자료 구조와 알고리즘] 정렬 - 퀵 정렬

 

 

 

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘

 

정렬 - 퀵 정렬

 

 

 

 

📍 퀵 정렬(Quick Sort)

👉🏻 병합 정렬과 같이 분할 정복 알고리즘에 속함

👉🏻 즉, 재귀를 사용함

피벗
 _
[5, 3, 7, 2, 6, 4, 9, 1, 8]

// 배열 중 하나를 피벗으로 설정
// 이해하기 쉽게 여기서는 제일 왼쪽 값을 피벗으로 설정

    _ leftStartIndex     _ rightStartIndex
[5, 3, 7, 2, 6, 4, 9, 1, 8]
 _                       _
left                    right

// leftStartIndex는 왼쪽에서 오른쪽으로 이동하다가 피벗보다 큰 수가 있으면 멈춤
// rightStartIndexs는 오른쪽에서 왼쪽으로 이동하는데 피벗보다 작은 수가 있으면 멈춤
// 둘 다 멈추면 값을 교환

피벗
 _        _        _
[5, 3, 1, 2, 6, 4, 9, 7, 8]

          _        _  
[5, 3, 1, 9, 6, 4, 2, 7, 8]

             _  _
[5, 3, 1, 2, 6, 4, 9, 7, 8]

[5, 3, 1, 2, 4, 6, 9, 7, 8] // leftStartIndex와 rightStartIndex가 만났음!

// 5와 비교해서 이동

[3, 1, 2, 4, 5, 6, 9, 7, 8]
 __________     ___________

// 5를 기준으로 왼쪽은 더 작고, 오른쪽은 더 큼!

... 

[1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

 

📍 퀵 정렬의 구현

[ quick_sort.mjs ]

function quickSort(arr, left, right) {
    if(left <= right) {
        let pivot = divide(arr, left, right); // 정렬된 피벗 위치(인덱스)를 리턴하는 함수 divide의 값을 저장
        quickSort(arr, left, pivot - 1); // 왼쪽 영역 정렬
        quickSort(arr, pivot + 1, right);
    }
}

function divide(arr, left, right) {
    let pivot = arr[left];
    let leftStartIndex = left + 1;
    let rightStartIndex = right;

    while(leftStartIndex <= rightStartIndex) {
        while(leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
            leftStartIndex++;
        }

        while(rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]) {
            rightStartIndex--;
        }

        if(leftStartIndex <= rightStartIndex) {
            swap(arr, leftStartIndex, rightStartIndex);
        }
    }
    
    swap(arr, left, rightStartIndex);
    return rightStartIndex;
}

function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

let arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];

console.log("===== 정렬 전 =====");
console.log(arr);

quickSort(arr, 0, arr.length - 1);

console.log("===== 정렬 후 =====");
console.log(arr);

👉🏻 퀵 정렬의 성능은 대부분 좋은 경우(Θ(nlogn))를 선택하고, 최악의 경우(O(n^2))가 발생할 확률이 낮음

👉🏻 즉, 퀵 정렬은 Θ(nlogn)의 성능을 가짐 

 

 

📍 퀵 정렬의 장단점

👉🏻 장점: 정렬 알고리즘 중 가장 좋은 성능

👉🏻 단점: 이해와 구현이 어려움