퀵소트는 아래와 같은 방법으로 정렬을 진행한다

  1. 배열의 요소 중 임의의 값을 pivot 으로 지정
  2. pivot 값을 기준으로 pivot보다 작거나 같은 값들은 왼쪽에 큰값들은 오른쪽에 위치시킨다
  3. 각 왼쪽과 오른쪽 배열에 대해서 요소의 개수가 0 또는 1이 될 때까지 위 1~2 과정을 반복한다

한줄요약

임의 값을 기준을 왼쪽/오른쪽 나누고 나뉘어진 상태에 대해서 동일한 작업을 재귀적으로 진행한다.


특징

  • 분할&정복
  • 불안정정렬
  • 시간복잡도: 최악 O(n^2), 평균 O(nLogn), 최선 O(nLogn)


간단한 js구현

아래 코드는 이해하기 쉽지만 O(nLogn) 공간복잡도 비용이 지불되는 단점이 있다

function quickSort(a){
    if(a.length < 2){
        return a;
    }
    var pivot = a[0];   // 첫번째 요소를 pivot으로 세팅
    var left = [];
    var center = [pivot];
    var right = [];
    for(var i=1; i<a.length; i++){
        if(a[i] > pivot){
            right.push(a[i])
        }else if(a[i] === pivot){
            center.push(a[i]);
        }else{
            left.push(a[i]);
        }
    }
    return [...quickSort(left), ...center, ...quickSort(right)];
}

quickSort([7,4,9,8,5,3,2,1,9,3]);
/*
[1, 2, 3, 3, 4, 5, 7, 8, 9, 9]
*/


아래와 같이 공간복잡도 O(1) 를 사용하는 구현도 가능하다. 하지만 코드의 디테일을 정확히 이해하기가 만만치 않다.

위 코드에서 가장 중요하게 다뤄져야할 부분은 partition 함수는 pivot값을 기준으로 양분된 배열에서 pivot 값의 위치를 리턴해야 한다 는 것이다

9라인에서 pivota[left] 값을 할당하고 루프(13~17라인) 안에서 최초로 pivot과 비교대상이 되는 a[i]값은 (i === left 이므로) pivot과 동일한 값이기 때문에 무조건 i값이 +1 증가 할테니 아예 처음부터 ileft+1 의 값을 할당하고 싶은 마음이 생길 수 있지만 그렇게 해서는 안된다.

ileft+1을 할당하면 길이 2인 배열이 입력으로 들어올 경우에 문제가 발생할 수 있다. (이 경우의 구체적인 동작에 대한 설명은 생략하겠다. 이 부분은 직접 코드를 돌려보며 각 실행단계를 확인해 보는 것이 내용을 정확히 이해하는데 더 큰 도움이 될 것이다)

그리고 루프(13~17라인) 안에 루프에서 j의 값을 감소시키는 루프(14라인)가 i를 증가시키는 루프(15라인)보다 앞서 위치해야 하는 것도 중요함을 주의해야 한다.


Ref

https://ko.wikipedia.org/wiki/퀵_정렬