정렬 (Sort) - 퀵정렬

퀵정렬이란?

• 퀵정렬(Quick Sort)은 또 다른 분할 정복 알고리즘,
• 배열을 하나의 피벗(pivot)을 기준으로 두 개의 부분 배열로 나누고 각각을 정렬하여 전체 배열을 정렬하는 방식.
• 퀵정렬은 평균적으로 매우 빠른 정렬 알고리즘 중 하나로 알려져 있음

퀵정렬 요약

특징	- 분할 정복 알고리즘 - 불안정 정렬 - 재귀적 접근 - 피벗 선택 중요
장점	- 평균적으로 매우 빠름 - 추가 메모리 공간이 거의 필요 없음(제자리 정렬)
단점	- 최악의 경우 O(n^2)의 시간복잡도 - 피벗 선택에 따라 성능이 좌우됨
시간복잡도	- 최선: O(n log n) - 평균: O(n log n) - 최악: O(n^2)
공간복잡도	- O(log n) (재귀 호출 스택 공간)

 

자바스크립트 예시

function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const pivot = array[Math.floor(array.length / 2)];
    const left = [];
    const right = [];

    for (let i = 0; i < array.length; i++) {
        if (i === Math.floor(array.length / 2)) continue; // 피벗은 넘김

        if (array[i] < pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }

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

// 테스트
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = quickSort(array);
console.log(sortedArray);

• 피벗 요소가 중간값일때