퀵 정렬

지난 번에 다룬 셸 정렬은 시간 복잡도가 O(n^2)로 아직 아쉬운 시간소모량을 보여줍니다. 그래서 더 빠른 정렬을 위해 고안된 방식이 퀵 정렬입니다.

---

1. 퀵 정렬

퀵 정렬은 가장 많이 사용되고 있는 가장 빠른 정렬 방식입니다. 정렬 대상을 특정 기준으로 두 개의 그룹을 나누고 다시 나눈 그룹에 대해 또 그룹을 나누고를 반복하여 정렬하는 방식입니다. 이때 특정 기준으로 설정하는 기준점을 피벗(Pivot)이라고 합니다. 퀵 정렬의 시간 복잡도는 O(n log n)입니다.

퀵 정렬 방식을 설명드리겠습니다. 우선 다음과 같은 배열이 있을 때 피벗을 설정합니다. 피벗은 보통 배열의 가운데 부분에 있는 요소에 대해 설정합니다.

피벗은 4로 설정해도 좋겠지만 6으로 설정하겠습니다.

그리고 피벗에 대해 피벗보다 작은 그룹, 피벗보다 큰 그룹으로 다시 두개의 그룹으로 나눕니다. 다시 나눈 두개의 그룹에 대해서 또 피벗을 설정하고 다시 두개의 그룹으로 나눕니다.

이 방식을 각 그룹의 요소가 1개가 될 때 까지 반복합니다.

이렇게 요소가 1개인 그룹만들이 남으면 이들을 다시 배열로 모아주기만 하면 정렬이 완료됩니다.

 

 

 

2. 퀵 정렬 구현

export const quickSort = arr => {
    let left = [];
    let right = [];
    let pivot = [arr[0]];

    //arr 요소가 1개 일땐 arr를 리턴하며 종료
    if (arr.length < 2) {
        return arr;
    };

    //반복문으로 arr 그룹을 순회합니다.
    for (let i = 1; i < arr.length; i++) {
        //피벗보다 작으면 피벗의 왼쪽 그룹으로
        if (arr[i] < pivot) {
            left.push(arr[i]);
        }
        //비벗보다 크면 피벗의 오른쪽 그룹으로
        else if (arr[i] > pivot) {
            right.push(arr[i]);
        }
        //피벗과 같으면 피벗에 넣기
        else {
            pivot.push(arr[i]);
        }
    }

    //재귀 함수로 남은 그룹에 대해 퀵 정렬을 실행한다.
    return quickSort(left).concat(pivot, quickSort(right));
};

import {quickSort} from './study-code/sort/quick-sort.js';

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

console.log(quickSort(arr));

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/quick-sort.js