[알고리즘] 정렬 - 빠른 정렬(퀵정렬, Quick Sort) (자바스크립트/javascript/node.js)

빠른 정렬(퀵 정렬, Quick Sort)

빠른 정렬(퀵 정렬)은 기준점을 획득한 다음 해당 기준점을 기준으로 배열은 나눈다.

(한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다.)

이런 식으로 모든 항목이 정렬될 때까지 이 과정을 반복한다.

우선 기준점을 나타내는 변수를 pivot이라고 지정하고, 기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 위치하도록 하고 오른쪽에는 기준점보다 큰 항목들이 위치하도록 한다.

 

나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 된다.

 

이 때 기준점을 정하는 기준은 없으며 보통의 경우에는 배열의 첫번째 원소 / 배열의 마지막 원소 / 물리적으로 중앙에 위치한 값을 기준점으로 정한다.

정렬하는 방법

퀵 정렬의 큰 흐름은 위에서 말한 것처럼 기준점(pivot)을 정하고, 기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 오게하고, 오른쪽에는 기준점보다 큰 항목들이 오게 정렬을 하면 된다고 했다. 그렇다면 본질적으로 정렬하는 방법은 어떻게 하는 것일까?

 

기준점(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한 정렬 방법(중복 값의 위치가 바뀔 수 있기 때문)

---

구현 (자바스크립트)

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]));