퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)은 병합 정렬과 동일하게 분할 정복(divide and conquer) 알고리즘을 기반으로 한 정렬 알고리즘이다. 퀵 정렬은 배열을 빠르게 정렬할 수 있는 효율적인 방법으로 알려져 있다.

퀵 정렬의 아이디어는 다음과 같다. 주어진 배열에서 하나의 요소를 선택하고, 이를 기준(pivot)으로 삼는다. 그리고 기준보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 분할(partition)한다. 이 분할된 부분 배열에 대해서도 동일한 과정을 반복하며, 분할된 부분 배열의 크기가 1이 될 때까지 반복한다. 이렇게 분할과정이 완료되면, 배열은 정렬되게 된다.

자바스크립트로 구현해보기

function quickSort(arr) {
  // 배열 요소가 1개 이하일 경우 이미 정렬된 상태
  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]); // 기준보다 큰 요소는 오른쪽으로
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

const arr = [6, 2, 9, 1, 5, 8];
const sortedArray = quickSort(arr);
console.log(sortedArray); // [1, 2, 5, 6, 8, 9]

위 코드에서 quickSort()함수는 재귀적으로 배열을 분할하고 정렬하는 과정을 수행한다. 기준(pivot)으로 선택한 요소를 기준으로 작은 요소는 left배열에, 큰 요소는 right배열에 분할한다. 그리고 left, right배열을 각각 재귀적으로 퀵정렬을 수행한 후, 이를 결합하여 정렬된 배열을 반환한다.

시간 복잡도

퀵정렬의 평균 시간복잡도는 O(n log n)이다. 최선의 경우에도 O(n log n)이지만, 최악의 경우에는 O(n^2)까지 증가할 수 있다. 하지만 일반적인 입력 데이터에 대해서 퀵정렬은 빠른 속도를 보여주며, 효율적인 정렬 알고리즘으로 널리 사용된다.