Quick Sort

퀵 정렬은 pivot을 기준으로 pivot보다 작은 경우 pivot기준 왼쪽으로, 클 경우 pivot기준 오른쪽으로 보낸 뒤, 해당 배열을 pivot을 기준으로 반으로 나누는 알고리즘
반으로 나뉜 배열은 다시 한번 위에 언급한 과정을 재귀적으로 수행한다.

시간 복잡도

• O(n log n)

코드

function swap(array, firstIndex, secondIndex) {
  let temp = array[firstIndex];
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
}

function pivot(array, pivotIndex = 0, endIndex = array.length - 1) {
  let swapIndex = pivotIndex;
  for (let i = pivotIndex + 1; i <= endIndex; i++) {
    if (array[i] < array[pivotIndex]) {
      swapIndex++;
      swap(array, swapIndex, i);
    }
  }
  swap(array, pivotIndex, swapIndex);
  return swapIndex;
}

function quickSort(array, left = 0, right = array.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
  }
  return array;
}