자바스크립트 핵간단한 퀵정렬 코드

 

퀵 정렬은 정렬 알고리즘이다. 선택 정렬보다 훨씬 빠르고 실제로도 많이 사용된다. C언어 표준 라이브러리에는 qsort라는 함수가 있는데 이것이 바로 퀵 정렬을 구현한 함수다. 퀵 정렬은 분할 정복 전략 중에 하나다.

 

배열을 정렬할 때 가장 간단하고 연산이 적은 배열은 무엇일까? 바로 정렬할 필요도 없는 배열이다.

 

• [] (비어 있는 배열)
• [5] (원소가 하나인 배열)

비어 있는 배열이나 원소가 하나인 배열이 기본 단계가 된다. 이 경우, 배열을 있는 그대로 반환하면 된다.

 

function quickSort(arr) {
    if (arr.length <= 1) return arr;
}

 

퀵 정렬은 분할 정복 전략 중에 하나이기 때문에, 배열을 기본 단계, 즉 비어 있는 배열이나 원소가 하나인 배열이 될 때까지 나눠야 한다. 퀵 정렬의 동작은 다음과 같다.

 

• 배열에서 원소 하나를 고른다.
• 기준 원소보다 작은 원소는 작은 원소의 배열, 기준 원소보다 큰 원소는 큰 원소의 배열로 분할한다.
• 하위 배열에 대해 재귀적으로 퀵 정렬 함수를 호출한다.

만약 [5, 13, 9]라는 세 개의 원소가 있다면, 처음에 quickSort([5, 12, 9])처럼 인자가 들어갔다가, 그 함수 내부에서 기준 원소를 한 개 골라 그 기준 원소보다 작은 원소들의 배열을 quickSort 해주고, 큰 원소들의 배열을 quickSort 해주면 된다.

 

return [...quickSort([]), [5], ...quickSort([13, 9])];

 

위에서는 기준 원소를 배열의 인덱스 0에 해당하는 원소로 골랐는데, 이 기준 원소로 무엇을 고르더라도 마찬가지로 작동한다. 개인적으로 그냥 for문에서 i가 1로 시작하여 쭉 한 바퀴 도는 것이 깔끔해 보여서 첫 번째 원소로 잡는 게 좋다. 사실 별 생각 없이 그렇게 공부했다.

 

다음은 퀵 정렬을 구현한 코드다. 

 

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    let middle = arr[0];
    let left = [];
    let right = [];
    
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < middle) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return [...quickSort(left), middle, ...quickSort(right)];
}