Quick Sort 구현

문제

평균적인 시나리오에서 시간복잡도가 낮기로 알려진 Quick Sort를 자바스크립트로 구현해본다.

예시

arr	result
[0, 5, 2, 1, 6, 3]	[0,1,2,3,5,6]
[3, 6, 0, 2, 4, 1, 7, 5]	[0,1,2,3,4,5,6,7]

풀이 (분할)

1. 퀵 정렬은 분할 이라는 개념에 기반한다.
2. 분할을 통해 배열에서 임의의 수를 가져와(여기서는 배열의 맨 오른쪽 수) 피벗으로 정하고, 피벗에서 작은 모든 수는 피벗의 왼쪽에, 큰 수는 피벗의 오른쪽에 둔다.
3. 두 개의 포인터 를 두는데, 왼쪽 포인터는 배열의 0번째 인덱스에서부터, 오른쪽 포인터는 피벗의 한 칸 앞 인덱스에서부터 시작한다.
4. 왼쪽 포인터가 가리키는 값이 피벗이 가리키는 값보다 크거나 같아질 때 까지 포인터를 계속 한 칸 씩 이동한다.
5. 왼쪽 포인터의 이동이 끝나면, 오른쪽 포인터의 이동을 시작하는데, 오른쪽 포인터는 피벗이 가리키는 값보다 작거나 같아질 때까지 포인터를 계속 한 칸 씩 이동한다.
6. 두 포인터의 이동이 끝나면, 두 포인터가 배열 내에서 만났는지 검사하고, 만났다면 왼쪽 포인터와 피벗을 바꾸고, 왼쪽 포인터를 반환하고 함수를 끝낸다. 그렇지 않다면 두 포인터의 위치를 바꾸고 4~6번 풀이를 반복한다.
7. 위 과정을 끝내면 피벗의 왼쪽에는 피벗보다 같거나 작은 숫자들만 모여있게 된다.

풀이 (퀵 정렬)

1. 분할에서 반환한 왼쪽 포인터를 피벗으로 두고, 피벗을 기준으로 왼쪽의 남은 원소들로 서브 배열을 만들어서 퀵 정렬 함수를 재귀로 실행시키고, 오른쪽 원소들로도 동일한 작업을 한다.
2. 위 분할에서 배열 내 원소의 개수가 1개 또는 0개일 때는 아무런 일도 일어나지 않으므로, 퀵 정렬 함수의 기저 조건을 퀵 정렬이 적용되는 원소의 개수가 1개 또는 0개일 때로 지정한다.

코드

class Sort {

    constructor(arr) {
        this.arr = arr;
    }

    partition (lPointer, rPointer){
        let pivot = rPointer;
        let pivotNum = this.arr[pivot];
        rPointer--;
    
        while (true) {
            while (this.arr[lPointer] < pivotNum) {
                lPointer++;
            }
            while (this.arr[rPointer] > pivotNum) {
                rPointer--;
            }
            if (lPointer >= rPointer) break;
            else this.swap(lPointer, rPointer);
        }
    
        this.swap(lPointer, pivot);
    
        return lPointer;
    }

    swap (lPointer, rPointer) {
        let tempValue = 0;
        tempValue = this.arr[lPointer];
        this.arr[lPointer] = this.arr[rPointer];
        this.arr[rPointer] = tempValue;
    }

    quickSort (lIndex, rIndex)  {
        if(rIndex - lIndex <= 0) return;
    
        const pivotPosition = this.partition(lIndex, rIndex);
        this.quickSort(lIndex, pivotPosition-1);
        this.quickSort(pivotPosition+1, rIndex);
      
        return this.arr;
    }
}

const arr1 = [0, 5, 2, 1, 6, 3];
const sortableArr = new Sort(arr1);
sortableArr.quickSort(0, arr1.length-1);

REFERENCE

누구나 자료 구조와 알고리즘 - 제이 웬그로우