[8][알고리즘 - 정렬] 퀵정렬(Quick Sort)이란? javascript 구현

 

퀵 정렬(Quick Sort)이란?

 

출처 - https://ezgif.com/speed/ezgif-4-42561febe484.gif

기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로,

큰 값을 지닌 데이터는 뒤로 가도록 하여

작은 값을 갖는 데이터와

큰 값을 갖는 데이터로 분리해가며

정렬하는 방법입니다.

 

이전에 만나봤던 합병정렬과 비슷하게

두 영역으로 분리하여 비교하는 정렬 방법입니다.

 

이렇게 두 영역으로 분리하여 각각을 해결하고

다시 합치는 전략을 분할 정복 방법이라고 합니다.

 

퀵 정렬의 원리를 좀더 간단하게 단계별로 나누면

아래와 같습니다.

 

1. 피벗을 설정한다.

2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 

3. 피벗을 기준으로 두개의 배열로 나눈다.

4. 각각의 배열을 1번부터 재귀적으로 반복한다.

 

 

// 위치 변경
const swap = (arr, leftIndex, rightIndex) => {
    const temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;
}


// 분할
const partition = (arr, start, end) => {
    const pivot = arr[end]; // 피벗 설정
    let left = start;
    for (let i = start; i < end; i++) {
        if (arr[i] < pivot) {
            swap(arr, i, left);
            left++;
        }
    }
    swap(arr, left, end);
    return left;
};

// 퀵 정렬
const quickSort = (arr, start, end) => {
    if (start >= end) {
        return;
    }

    let index = partition(arr, start, end);

    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}

// 임의 배열 생성
const makeRandomValueArr = (length) => {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }

    for (let i = 0; i < arr.length; i++) {
        const randomNum = Math.floor(Math.random() * arr.length);
        [arr[i], arr[randomNum]] = [arr[randomNum], arr[i]];
    }

    return arr;
}

// 실행

const arr = makeRandomValueArr(10);

console.log('arr==', arr);
// [4, 3, 2, 5, 1, 8, 6, 7, 9, 0]
console.time('quick');
quickSort(arr, 0 , arr.length -1);
console.timeEnd('quick');

console.log('result==', arr);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]