Quick Sort(퀵정렬)

Quick Sort란?

퀵정렬은 병합정렬과 비슷한 분할 및 정복 방법이다. 차이점은 pivot값을 사용한다는 것이다.

커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘이다.

(커다란 크기의 입력에서는 Merge Sort보다 평균적으로 성능 더 좋음)

 

문제를 2개의 부분문제로 분할한다. 각 부분문제의 크기가 일정하지 않은 형태의 분할정복 알고리즘이다.

퀵정렬의 아이디어는, 피봇이라는 배열 원소 값을 기준으로,

피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓는다.

퀵정렬의 성능은 피봇선택이 좌우한다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되면, 한 부분으로 치우치는 분할을 야기한다.

 

최선/평균의 경우 O(nlogn) : 각 층에는 각각의 원소가 각 부분의 피봇과 1회씩 비교된다. O(n). 층수를 곱한다. O(n)*(logn)

최악의 경우 O(n**2)

 

성능을 향상시키기 위해서는, 부분문제의 크기가 작아지면 삽입 정렬을 동시에 사용한다.

 

예시

데이터가 [66, 77, 54, 32, 10, 5, 11, 15]라고 가정한다.

피봇값: 66

[54, 32, 10, 5, 11, 15] + [66] + [77]

 

피봇값: 54

[32, 10, 5, 11, 15] + [54] + [66] + [77]

 

피봇값: 32

[10, 5, 11, 15] + [32] + [54] + [66] + [77]

 

피봇값: 10

[5] + [10] + [11, 15] + [32] + [54] + [66] + [77]

 

피봇값: 11

[5] + [10] + [11] + [15] + [32] + [54] + [66] + [77]

 

코드

function quickSort(arr) {
    let arrLen = arr.length;

    if (arrLen <= 1) {
        return arr;
    }

    let pivot = [arr.shift()];
    let group1 = [];
    let group2 = [];

    for (let i in arr) {
        if (arr[i] < pivot) {
            group1.push(arr[i]);
        } else {
            group2.push(arr[i]);
        }
    }

    console.log(`그룹하나: ${group1}\n 그룹둘: ${group2}\n 피봇값: ${pivot}`);

    return quickSort(group1).concat(pivot, quickSort(group2));
}

console.log(quickSort(data));