[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 16: 퀵 정렬)

섹션 16: 퀵 정렬

이 코드는 배열에서 가장 왼쪽의 값을 피봇으로 삼는 방식으로 작성되어 있다. 피봇 값 보다 작은 값은 피봇 값 왼쪽에 위치하도록 하는 정렬 방식으로 재귀 함수를 이용해 이 과정을 반복하여 정렬한다. 

function pivot(arr, start = 0, end = arr.length + 1) {
    function swap(arr, i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }

    var pivot = arr[start]
    var swapIdx = start

    for (var i = start + 1; i < arr.length; i++) {
        if (pivot > arr[i]) {
            swapIdx++
            swap(arr, swapIdx, i)
        }
    }
    swap(arr, start, swapIdx)

    return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        let pivotIndex = pivot(arr, left, right)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)
    }
    return arr
}

console.log(quickSort([4, 8, 2, 1, 5, 7, 6, 3]))

 

Big O

이미 오름차순, 혹은 내림 차순으로 정렬된 경우와 같이 배열에서 최솟값, 혹은 최댓값이 피봇으로 선택되는 경우 최악의 시간 복잡도를 가질 수 있다.

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Quick Sort	O(n log n)	O(n log n)	O(n2)	O(log n)