Quick Sort ( 퀵 정렬 )

Quick Sort

퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다.

이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다.

퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다.

in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그 다음 in place 방법을 정리하겠다.

Basic Quick Sort - Not In Place

퀵 정렬은 분할정복 전략을 사용한 알고리즘이다.

즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 있는 배열이므로 모든 배열이 기본 배열이 될 때까지 큰 배열을 나눠야한다.

이 때 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다.

그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.

pivot 왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다. 이 방법을 반복하면 결국 기본 단계인 원소가 하나만 있는 배열이 남는다.

 

- js 로 코드를 구현 해보겠다.

function 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]);
      }
    }
    console.log("left :",left , "pivot:", pivot, "right:", right);
    return quickSort(left).concat(pivot, quickSort(right));
    // return에서 다시 함수를 불러와 배열의 요소가 하나만 남을 때까지 돌린다.
  }
  
  const array = [12,4,1,2,3,13,64,3]
  
  console.log(quickSort(array));

- OUTPUT

left : [ 4, 1, 2, 3, 3 ] pivot: 12 right: [ 13, 64 ]
left : [ 1, 2, 3, 3 ] pivot: 4 right: []
left : [] pivot: 1 right: [ 2, 3, 3 ]
left : [] pivot: 2 right: [ 3, 3 ]
left : [] pivot: 3 right: [ 3 ]
left : [] pivot: 13 right: [ 64 ]
[ 1, 2, 3, 3, 4, 12, 13, 64 ]

1. 기준 원소를 고른다. 여러 가지 방법이 있겠지만 위 그림에서는 배열의 첫 번째 요소를 기준 원소로 설정했다.
2. 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 2개의 하위 배열로 분할한다.
3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.

위 방법의 퀵 정렬은 in place 방법이 아니기 때문에 별도의 메모리 공간이 필요하므로 데이터의 양이 많으면 공간적인 낭비가 심해져 실제로는 잘 쓰이지 않는 방법이다.

그러나 위의 방법으로 퀵 정렬을 할 경우에 중복되는 데이터는 순차적으로 pivot에 넣으면 되기 때문에 정렬 전 중복 데이터의 순서가 바뀌지 않는 stable한 정렬을 구현할 수 있다.

 

In place Quick Sort

위의 방법은 이해하기에 훨씬 쉽고 구현도 간단하지만 메모리 공간의 낭비가 심하기 때문에 위 방법보다는 in place 방법이 훨씬 더 많이 사용된다.

 

function quickSort(array, left = 0, right = array.length - 1) {
  if (left >= right) {
    return;
  }
  const mid = Math.floor((left + right) / 2);
  const pivot = array[mid];
  const partition = divide(array, left, right, pivot);
  quickSort(array, left, partition - 1);
  quickSort(array, partition, right);

  function divide(array, left, right, pivot) {
    while (left <= right) {
      while (array[left] < pivot) {
        left++;
      }
      while (array[right] > pivot) {
        right--;
      }

      if (left <= right) {
        let temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left++;
        right--;
      }
    }
    return left;
  }
  return array;
}
console.log(quickSort([1, 12, 5, 26, 7, 14, 3, 7]));

 

기준점(pivot)을 정한 후(나는 물리적으로 중앙에 위치한 값을 기준점으로 하겠다)

left(위의 그림에서는 i) , right(위의 그림에서는 j) 라는 인덱스를 정한다.

left의 초기값은 배열의 첫번째 인덱스가 되고, right의 초기값은 배열의 가장 마지막 인덱스가 된다.

 

우리는 기준점을 기준으로 왼쪽에는 기준보다 작은 값만 위치해야 하니까, 기준보다 큰 값이 존재하면 안될 것이다.

마찬가지로 오른쪽에는 기준보다 큰 값만 위치하길 원하므로 기준보다 작은 값이 존재하면 안된다.

그러므로 left는 pivot보다 큰 값이 나올 때까지 오른쪽으로 움직인다(left++)

마찬가지로 right는 pivot보다 작은 값이 나올 때까지 왼쪽으로 움직인다(right--)

그리고 나서 pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다.

 

그러다가 left와 right가 역전되어버리는 순간 (left가 right보다 커지면) 반복문을 멈추고 당시의 left를 반환하여

그 left를 partition인덱스로 삼아서 두 배열로 갈라서 각 하위 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다. 

 

시간 복잡도

- 평균

 O(nlog₂n) (평균적으로 O(nlog₂n) 이지만, 보통 O(nlog₂n)보다 빠르다.)

 결국 모든 배열이 기본 배열이 될 때까지 나누기 때문에 n번 나누게 되고, 한 번 나눌 때마다 검색해야 하는 데이터가 절반으로 줄어버리니까 logn인 것이다. 빠르기로 유명한 합병정렬보다 보통 더 빠르기 때문에 더 자주 쓰인다.)

 

- 최악의 경우: O(n^2)

 기준(pivot)으로 뽑은 수가 항상 제일 큰 수이거나 제일 작은 수일 경우

 

공간 복잡도

추가적인 공간을 필요로 하지 않는 in-place 알고리즘 -> 메모리 절약

unstable한 정렬 방법(중복 값의 위치가 바뀔 수 있기 때문)