[Algorithm] 퀵 정렬(Quick Sort) Javascript, Node.js 구현하기 (백준 2751 수 정렬하기 2)

 

퀵 정렬(Quick Sort)

 

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 퀵 정렬은 재귀 알고리즘을 사용해 pivot과 positioning을 지정하면서 컴퓨터 아키텍처에서 메모리 효율적으로 작동하도록 작성된다. 퀵 정렬의 시간복잡도는 최악의 경우 O(N^2)이지만, 평균적인 시간복잡도는 O(N log N)이 된다.

 

퀵 정렬을 사용하게 되면 최악의 경우를 만나게 되는 경우는 극히 드물며, 매 단계에서 적어도 1개의 원소가 정렬되기 때문에 이후 정렬할 개수는 점점 줄어들게 된다. 또한 원소들 중 같은 값이 있는 경우 위치가 달라질 수 있기 때문에 속도는 빠르지만 정렬의 정확성에 대해서는 불완전 정렬에 속하고 있다.

 

출처 : 위키백과 퀵 정렬

 

 

퀵 정렬(Quick Sort) 알고리즘 구현

 

퀵 정렬 알고리즘을 떠받치고 있는 알고리즘은 분할정복 알고리즘이다. 

① 주어진 배열에서 하나의 원소를 고르고, 이를 pivot으로 지정한다.

② pivot 앞에는 pivot 보다 작은 원소들이 위치한다. pivot 뒤에는 pivot 보다 큰 원소들이 위치하게 된다. 즉 pivot을 기준으로 주어진 배열을 둘로 분할하게 된다. 분할이 된 리스트는 더 이상 변경되지 않는다.

③ 분할된 두개의 리스트에 대해 리스트의 길이가 1보다 작거나 같은 경우 까지 재귀적인 호출을 진행한다. 재귀 호출을 진행할 때 최소한 1개의 원소의 위치가 지정되므로, RangeError: Maximum call stack size exceeded 범위 에러가 발생하지 않는다.

예를 들어 arr = [5,2,3,1,4,6] 을 정렬한다고 가정하자. pivot은 가장 첫번째 요소 5로 지정한다. i는 5, j는 6으로 지정한다. pivot을 기준으로 큰 값은 오른쪽에 작은 값은 왼쪽에 위치해야 한다. i는 증가시키면서 pivot보다 큰 값이 있는지 찾고, j는 감소시키면서 pivot보다 작은 값이 있는지 확인한다. 이 경우 4는 pivot보다 작은 값이기 때문에 i와 j의 요소를 교환한다. 교환된 값으로 pivot을 새로 지정하고 이를 분할이라고 한다.

 

 

새로 지정된 pivot 5를 기준으로 왼쪽과 오른쪽으로 영역이 구분된다. 이제 왼쪽 영역과 오른쪽 영역의 길이가 1이 될 때 까지 재귀적인 호출을 진행한다. 오른쪽 영역은 길이가 1이기 때문에 재귀적인 호출을 진행하지 않고, [6]을 그대로 반환한다. 왼쪽의 경우 pivot은 4로 지정하고 i를 증가시키면서 pivot보다 큰 값이 있는지 확인하고, j를 감소시키면서 pivot보다 큰 값이 있는지 확인한다. 모든 리스트를 확인한 후 값을 찾지 못하면서 i와 j의 값이 역전되는 경우 현재 i와 j의 위치를 변경시킨다.

 

위 과정을 거치고 나면 모든 리스트가 정렬된 상태로 정해진다. 

 

 

Node.js 구현 1

/*
    문제 : 백준 수 정렬하기 2 
    날짜 : 2022-06-05
    작성 : About-Tech
*/

const readline = require('readline');
const { stdin : input, stdout : output } = require('process');

const rl = readline.createInterface({input, output});

let N;
let count=0;
let inputValue = [];
rl.on('line', (line)=>{
    count++;
    inputValue.push(parseInt(line));
    N = inputValue[0];


    if(N === count-1){
        const [start, ...arr] = inputValue;

        inputValue = quicksort(arr, 0, arr.length-1);

        // 출력값은 string 타입으로 반환
        const result = inputValue.join('\n');
        console.log(result);

        rl.close();
    }
    
})


rl.on('close', ()=>{
    process.exit();
})

function quicksort (arr, left, right){
    if(left < right){
        // 새로운 position 지정
        let i = position(arr, left, right);
        
        // 왼쪽 영역에 대해 재귀적인 호출
        quicksort(arr, left, i-1);
        // 오른쪽 영역에 대해 재귀적인 호출        
        quicksort(arr, i+1, right);
    }

    return arr;
}

function position(arr, left, right){
    let i = left;
    let j = right;
    let pivot = arr[left];

    while(i<j){
        // pivot 기준으로 오른쪽 영역은 큰 값이 위치한다.
        while(arr[j]>pivot) j--;
        // pivot 기준으로 왼쪽 영역은 작은 값이 위치한다.
        while(i<j && arr[i]<= pivot) i++;

        // i와 j가 역전되는 경우 정렬진행
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 새로운 pivot 지정
    arr[left]  =arr[j];
    arr[j] = pivot;

    return j;
}

 

Node.js 구현 2

위 코드와 동일한 로직으로 구성되었지만, 코드가 한결 간단한다. 먼저 pivot을 지정하고, 전달받은 arr을 순회하면서 pivot을 기준으로 왼쪽 오른쪽으로 구분한다. 이 후 leftSorted와 rightSorted에 개별적으로 재귀함수를 호출해 정렬된 배열을 반환받는다. 최종적으로 스프레드 연산자를 사용해 전체 배열을 나열해 출력한다.

const quickSort = (arr) => {
    if(arr.length <= 1) return arr;

    const pivot = arr[0];
    const left = [];
    const right = [];

    for(let i=1; i<arr.length; i++){
        if(arr[i] <= pivot) left.push(arr[i]);
        else right.push(arr[i]);
        
    }

    const leftSorted = quickSort(left);
    const rightSorted = quickSort(right);

    return [...leftSorted, pivot, ...rightSorted]
}

 

Node.js 구현 3

동일한 퀵 정렬이지만, callback을 인수로 전달받은 경우다. callback의 결과값을 통해 배열 요소들을 비교한 후 original 배열을 반환한다.

const quickSort = (arr, callback) => {
    if(arr.length <= 1) return arr;

    const pivot = arr[0];
    const left = [];
    const right = [];

    for(let i=1; i<arr.length; i++){
        if(callback){
            if(callback(arr[i]) <= callback(pivot)) left.push(arr[i]);
            else right.push(arr[i]);
        }else{
            if(arr[i] <= pivot) left.push(arr[i]);
            else right.push(arr[i]);
        }
    }

    const leftSorted = quickSort(left);
    const rightSorted = quickSort(right);

    return [...leftSorted,pivot,...rightSorted]
}

 

백준 2751번 수 정렬하기 2번 문제가 퀵 정렬로 풀어보는 문제다. 하지만 퀵 정렬로 알고리즘을 구성하면 시간초과가 발생한다. 퀵 정렬 특성상 최악의 경우 모든 요소를 점검해야 하기 때문에 시간복잡도가 O(N^2)이 되는데, 이를 저격한 데이터가 포함된 것으로 추측됨. 문제 TIP에서 말해주듯이 어려운 정렬 알고리즘이기 때문에 간단한게 sort() 내장 메서드를 사용하라고 친절하게 안내하고 있다.

 

백준 2751 수 정렬하기 2번 문제를 풀기위해서 sort() 내장 메서드를 사용해서 배열을 정렬하고, 문자열에 담아 한번에 출력하면 문제는 시간초과 없이 통과된다. 하지만 시간복잡도 O(N long N)을 가지는 퀵 정렬이나 병합 정렬로 풀어보라는 문제기 때문에 개념은 알고 있을 것!

let result = '';
inputValue = arr.sort((a,b)=>a-b)
const result = inputValue.join('\n');

console.log(result);

 

 

Reference

• 퀵 정렬이란? [위키백과]

 

 

 

[Algorithm] 백준 2447번 별 찍기 - 10 Node.js Javascript

 

[Algorithm] 백준 10818번 최소 최대 문제 Node.js 여러줄 입력 받기

 

[Algorithm] 분할정복 거듭제곱 분할제곱 알고리즘 Javascript