정렬 알고리즘 - 퀵 정렬

퀵 정렬(Quick Sort)

• 병합 정렬과 마찬가지로 분할 정복 알고리즘을 이용한 정렬 알고리즘이며 가장 빠른 정렬 알고리즘 중 하나이다.
• 정렬하는데 가장 간단한 배열인 요소가 없거나 요소가 하나만 있는 배열이 될 때까지 큰 배열을 나눠야한다.
• 요소 하나를 기준 원소인 pivot으로 설정한다. 그리고 pivot의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.
• 나누어진 하위 배열들을 재귀적으로 정렬한다.

시간복잡도

• 최선의 경우 : O(nlog₂n)
• 최악의 경우 : O(n^2)
  
  

장점

• O(nlog₂n)인 다른 정렬 알고리즘과 비교해도 속도가 빠르다.
  
  

단점

• 정렬된 데이터들에 대해서 최악의 시간 복잡도가 나오게 된다.
• 즉, 정렬된 배열의 첫 번째 원소를 기준으로 퀵 정렬을 진행하게 되는 경우.
  
  

구현

// 가장 대표적인 호어방식 퀵 정렬 알고리즘 구현
const quickSort = (array, start = 0, end = array.length - 1) => {
  if (start >= end) return; // 원소가 1개인 경우 종료

  let partitionIndex = partition(array, start, end);

  quickSort(array, start, partitionIndex - 1);
  quickSort(array, partitionIndex + 1, end);

  return array;
};

const partition = (array, start, end) => {
  // console.log("partition start");
  const pivotValue = array[start];
  const pivotIndex = start;
  let left = start + 1;
  let right = end;

  while (left <= right) {
    // pivot 보다 큰 데이터를 찾기 => 시작 부분 부터
    while (left <= end && array[left] <= pivotValue) left++;

    // pivot 보다 작은 데이터를 찾기 => 끝 부분 부터
    while (right > start && array[right] >= pivotValue) right--;

    // index가 엇갈린 경우 작은 데이터(array[right])와 pivot 교체
    if (left > right) {
      swap(array, right, pivotIndex);
    } else {
      swap(array, left, right);
      left++;
      right--;
    }
  }

  return right;
};

const swap = (array, front, back) => {
  [array[front], array[back]] = [array[back], array[front]];
};

const array = [38, 27, 43, 3, 9, 82, 10];
console.log(quickSort(array));