퀵 정렬

July 28, 2023

퀵 정렬이란

퀵 정렬은 분할 및 정복 기반 알고리즘이며, 요소를 피벗으로 선택하고 정렬된 배열의 올바른 위치에 피벗을 배치하여 선택된 피벗을 중심으로 주어진 배열을 분할합니다.

퀵 정렬하는 과정을 간단히 정리하면 다음과 같습니다.

분할: 입력 배열을 피벗을 기준을 비균등하게 2개의 부분 배열(피벗보다 작은 요소들, 피벗보다 큰 요소들)로 분할합니다.
정복: 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할하여 같은 과정을 진행합니다.
결합: 정렬된 부분 배열들을 하나의 바열에 합병한다.

퀵 정렬 동작 과정

배열 [10, 80, 30, 90, 40]을 예를 들어 살펴 보겠습니다.

피벗은 40으로 합니다. 입력된 배열에 피벗을 기준으로 작은값, 큰값으로 나눕니다.
```
[10, 30] 40 [90, 80]
```
왼쪽 배열에서 피벗을 30으로 합니다. 입력된 배열에 피벗을 기준으로 작은값, 큰값으로 나눕니다
```
[10] 30
```
왼쪽 배열에서 피벗을 80으로 합니다. 입력된 배열에 피벗을 기준으로 작은값, 큰값으로 나눕니다.
```
80 [90]
```
해당 과정이 각각 분할된 배열의 크기가 0, 1이나 될때까지 반복하고, 그 이후에는 결합합니다.
```
[10, 30, 40, 80, 90]
```

퀵 정렬 구현 코드

function partition(arr, low, high) {
  // 가장 오른쪽 값을 피벗으로 설정
  const pivot = arr[high];

  // 피벗 왼쪽에 작은 요소들을 넣기 위한 index
  let i = low - 1;

  for (let j = low; j <= high - 1; j++) {
    // 피벗보다 작은 요소를 찾아
    if (arr[j] < pivot) {
      // Increment index of smaller element
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  // 피벗을 알맞은 위치에 넣기
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

  // 피벗을 반환한다
  return i + 1;
}

function quickSort(arr, low, high) {
  if (low >= high) {
    return;
  }

  // 분할
  const pivot = partition(arr, low, high);

  // 피벗 기준을 왼쪽, 오른쪽 배열을 재귀적으로 호출하여 정렬하는 과정 (정복)
  quickSort(arr, low, pivot - 1);
  quickSort(arr, pivot + 1, high);
}

const arr = [10, 7, 8, 9, 1, 5];

quickSort(arr, 0, arr.length - 1);

시간 복잡도 & 공간 복잡도

시간 복잡도

퀵 정렬의 최악의 경우 시간 복잡도는 O(n^2)입니다.
퀵 정렬의 평균적인 경우의 시간 복잡도는 O(nlogn)입니다.
최선의 경우의 시간 복잡도는 O(nlogn)입니다.

공간 복잡도

퀵 정렬의 공간 복잡도는 재귀 스택 공간을 고려하지않으면 O(1)이고 고려하면 O(N)입니다.

퀵 정렬의 특징

대용량 데이터에서 효율적입니다.
최악의 경우 O(N^2)의 시간 복잡도를 가집니다. (피벗이 잘못 선택되었을 때 발생합니다.)
작은 데이터에서는 적합하지 않습니다.
안정적인 정렬이 아닙니다. 즉, 두 요소의 키가 동일한 경우 퀵 정렬의 경우 정렬된 출력에서 상대적인 순서가 유지되지 않습니다.

참조

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

https://www.geeksforgeeks.org/quick-sort/

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html