Quick sort

과정

1. 배열 중 하나의 요소를 골라 피벗(pivot) 포인트를 설정한다.

2. 피벗 포인트를 기준으로 좌측에는 피벗보다 작은 값, 우측에는 피벗보다 큰 값이 오도록 정렬한다.

3. 재귀함수를 이용하여 정렬하는 값의 길이가 1이 될 때 까지 반복한다.

예제 코드

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (array, idx1, idx2) => {
    [array[idx1], array[idx2]] = [array[idx2], array[idx1]];
  };

  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  swap(arr, start, swapIdx);
  return swapIdx;
}

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

  return arr;
}

시간 복잡도 = O(n log n)

최악의 경우(오름차순, 내림차순으로 정렬되어 있을 경우) = O(n^2)

공간 복잡도 = O(n)

다른 분들이 작성한 코드 (훨씬 직관적이다..)

function quicksort(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    let pivot = arr[0]; // 재귀단계 (10 -> 기준 원소)

    let less = [];
    let greater = [];

    for (let i of arr) {
      if (i < pivot) {
        less.push(i); // 기준원소보다 작은 원소로 이루어진 배열
      } else if (i > pivot) {
        greater.push(i); // 기준 원소보다 큰 원소로 이루어진 배열
      }
    }

    return [...quicksort(less), pivot, ...quicksort(greater)];
  }
}