퀵 정렬(Quick Sort)

📌 퀵 정렬

병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다.

pivot(중심축) 을 정하고, 중심축 보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보낸다.
이렇게 pivot을 정해서 왼쪽, 오른쪽으로 나누고 다시금 이에 대해 재귀적으로 pivot을 정해서 왼쪽, 오른쪽을 나누는 과정을 반복하면 최종적으로 정렬이 완성된다.

 

퀵정렬의 실행시간은 피벗 선택 위치에 따라 달라질 수 있는데 이상적으로는 데이터 집합의 중간값을 피벗으로 선택하는 것이다.

하지만 데이터의 중간값을 구하기 어려운 상황이라면 첫 번째 요소 또는 마지막 요소 또는 중간, 무작위 요소를 선택한다.

 

 

 

👀 Example

const quickSort = function (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 lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

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

👀 Example 2

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 swap = array[left];
        array[left] = array[right];
        array[right] = swap;
        left++;
        right--;
      }
    }
    return left;
  }
 
  return array;
}

먼저 배열의 왼쪽 인덱스와 오른쪽 인덱스의 기본값을 각각 0과 array.length - 1로 설정한다.
그리고 중간 pivot값을 구한다.
divide라는 함수를 통해 왼쪽과 오른쪽 인덱스를 이동하며 값을 교환하고 partition으로 설정할 인덱스를 리턴받는다.

리턴받은 partition 인덱스를 기준으로 배열을 왼쪽 배열, 오른쪽 배열로 나눠서 다시 재귀 호출을 한다.

 

[참고]

https://im-developer.tistory.com/135

[JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기 (Quick Sort in JavaScript)