[Udemy] 퀵 정렬(Quick Sort)이란?

 

정의

배열에 1개 이하의 요소가 남을 때 까지 분할하여 정렬한다.

"피벗 포인트"라는 단일 요소를 선택하여 오름차순 정렬 시 이보다 작은 숫자를 좌측으로 이동시키고

이보다 큰 숫자는 그대로 둔다.

 

 

접근

퀵 정렬도 병합 정렬과 비슷한 가정으로 분할(split) → 정렬(sort) 로직으로 접근할 수 있는데,

병합 정렬은 index의 중간을 기준으로 정했다면, 퀵 정렬은 "피벗 포인트"라는 단일 요소를

직접 지정하여 정렬을 할 수 있다.

 

 

"피벗 포인트"는 처음, 중간, 끝 모두 지정할 수 있는데,

이해를 돕기 위해 처음으로 지정해두자.

 

코드

1. Pivot helper 함수 구현

 

우선, 피벗 포인트를 기준으로 모든 요소가 피벗 포인트보다 큰지, 작은지만 판단하여 좌,우로 정렬한다.

이 때, 좌, 우 정렬된 요소들의 순서는 상관하지 않는다.

왜냐하면 재귀를 통해서 접근할 것이기 크게 상관이 없다.

 

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

    let pivot = arr[start]
    let swapIdx = start;

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

    swap(arr, start, swapIdx);
    return swapIdx;
}

pivot([4,6,9,1,2,5]) // arr = [2, 1, 4, 6, 9, 5] , swapIdx = 2

 

 

피벗 포인트를 시작점으로 지정했으니 pivot 변수값을 첫번째 요소로 지정한다.

스왑할 인덱스를 의미하는 swapIdx에는 초기 start 변수를 할당한다.

 

 

pivot 이후 요소부터 비교하여 pivot보다 작을 경우 swapIdx를 이동시킨 뒤 swap을 진행한다.

(이 부분이 잘 이해가 안될 수 있다.)

 

 

pivot 이후 모든 요소의 순회가 끝나면

swapIdx는 pivot 요소보다 작은 값을 가진 요소의 갯수와 동일하다.

pivot 요소와 swapIdx 요소를 swap하여

pivot 요소 보다 작은 요소들 중 제일 마지막 위치로 pivot 요소를 이동시킨다.

 

 

2. quickSort 구현

 

이제 pivot 함수를 구현했으니 이후 로직을 구현해보자.

처음 pivot 함수를 호출하여 swapIdx를 구한 후 swapIdx를 기준으로

왼쪽 배열과 오른쪽 배열이 나뉘게 된다.

 

 

왼쪽 배열을 구간만큼 quickSort 함수를 재귀 호출한다.

그리고 오른쪽 배열 구간만큼 quickSort 함수를 재귀 호출한다.

 

종료 조건은 왼쪽 시작인덱스(left)가 오른쪽 끝 인덱스(right)보다 크거나 같을 때 종료된다.

 

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

 

시간복잡도

 

가장 좋은 경우, pivot 포인트가 배열의 중간에 위치하는 순서일 경우이다.

예를 들어, 64개의 요소가 있는 배열에서 매 재귀 호출 시마다 left, right에 입력값이 절반으로 줄어드는 경우다.

 

 

이 경우에선 O(log n) 시간 복잡도를 가지며, 절반으로 분해된 후 각각의 단계에서 pivot 함수를 호출하여 비교할 때

시간 복잡도 O(n)을 가지므로 시간 복잡도 O(n log n)을 가진다.

 

 

만약 가장 안좋은 경우는 이미 정렬된 배열을 전달했을 때이다.

이미 정렬된 배열인 경우, 분해 결과 O(n)의 시간복잡도를 가지며 pivot 함수 호출 비교 시 O(n)의 시간복잡도 가지므로

시간 복잡도 O(n^2)을 가지게 된다.

 

 

즉, 최솟값 또는 최댓값을 선택할 경우 최악의 경우의 수가 발생하는 것이다.

 

참조

Udemy - Js 알고리즘 & 자료구조 강의