[알고리즘] 퀵 정렬 알고리즘 With JS

퀵 정렬

이 알고리즘은 먼저 배열의 한 요소를 피벗(pivot)으로 선택한 후, 피벗보다 작은 요소는 모두 피벗의 왼쪽에 위치하도록, 피벗보다 큰 요소는 모두 피벗의 오른쪽에 위치하도록 배열을 분할합니다. 

 

그 다음, 분할된 두 하위 배열을 각각 재귀적으로 퀵 정렬을 수행하여 정렬을 완료합니다.

이 알고리즘의 핵심 아이디어는 분할(Divide) 단계에서 피벗을 기준으로 배열을 분할하여 정복(Conquer) 단계에서 각 하위 배열을 정렬하는 것입니다. 이 과정을 반복하여 분할된 배열이 더 이상 분할되지 않을 때까지 정렬을 수행합니다.

 

피벗 요소를 기준으로 해당 요소보다 작은 요소는 좌측으로, 큰 요소를 우측으로 분할하여, 배열을 분할한다. 그 후 분할 된 배열 내에서 재귀적 퀵 정렬(퀵 정렬 함수를 다시 호출)을 실행하여, 각 분할된 배열들의 요소가 더 이상 분할이 불가능해질 때 까지 각 배열에 대한 재귀적 퀵 정렬을 반복한다.

---

퀵 정렬 코드

function quickSort(arr) {
  // 1. 배열의 길이가 1 이하이면 배열을 반환합니다. (기저 조건)
  if (arr.length <= 1) {
    return arr;
  }

  // 2. 배열에서 중간 값을 피벗(pivot)으로 선택합니다.
  // 편의상 중간값으로 정한 것일 뿐 어느 요소가 피벗이 되어도 상관 없습니다.
  // 단, 피벗의 선정 방식에 따라 시간복잡도는 차이가 날 수 있습니다.
  // 즉, 어떤 요소를 피벗으로 선택해도 퀵 정렬은 정상적으로 실행됩니다.
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];
  const left = [];
  const right = [];

  /** --- 배열을 left 배열과 right 배열로 분할하는 구간입니다.
     3. 배열을 순회하면서, 피벗을 기준으로 
         '작은 값'은 [왼쪽 배열]에, 
         '큰 값'은 [오른쪽 배열]에 추가합니다.
  */
  for (let i = 0; i < arr.length; i++) {
    if (i === pivotIndex) {
      // 현재 요소가 피벗이라면, 다음 요소를 처리합니다.
      continue;
    }

    if (arr[i] < pivot) {
      // 현재 요소가 피벗보다 작으면, 왼쪽 배열에 추가합니다.
      left.push(arr[i]);
    } else {
      // 현재 요소가 피벗보다 크면, 오른쪽 배열에 추가합니다.
      right.push(arr[i]);
    }
  }
   /** 정렬된 각 배열에 대한 정복(합치는) 구간입니다. 정렬될 때 까지 각 배열은 재귀호출을 실시합니다. */
   // 4. 왼쪽 배열과 오른쪽 배열을 각각 재귀적으로 `quickSort()` 함수를 호출하여 정렬된 배열을 반환합니다.
  return [...quickSort(left), pivot, ...quickSort(right)];
}

---

시간복잡도와 공간복잡도

퀵 정렬의 시간 복잡도와 공간 복잡도는 피벗의 선택 방법과 분할 시에 어떻게 하위 배열을 나누는지에 따라 달라집니다.

---

• 최적 시간 복잡도(O(n log n))

최적의 경우, 피벗을 항상 중앙값으로 선택하는 경우입니다. 이 경우, 분할할 때 항상 두 개의 균등한 하위 배열이 생성되므로, 전체 배열을 O(log n)번만큼 분할하면 됩니다. 각 분할 단계에서 배열을 처리하는 데 걸리는 시간은 O(n)이므로, 최적 시간 복잡도는 O(nlogn)입니다.

 

---

• 보통 시간 복잡도(O(n log n))

보통의 경우, 피벗의 선택 방법이나 하위 배열을 나누는 방법에 따라 시간 복잡도가 달라집니다. 피벗이 양쪽으로 골고루 분포되어 있는 경우, 분할할 때 항상 균등한 하위 배열이 생성되므로 최적 시간 복잡도와 같습니다.

 

그러나, 피벗이 최솟값이나 최댓값으로 선택되는 경우, 배열이 한 쪽으로만 쌓이게 되어 분할이 제대로 이루어지지 않을 수 있습니다. 이 경우 시간 복잡도가 O(n^2)까지 증가할 수 있습니다.

 

이를 방지하기 위해 피벗의 선택 방법을 최적화하는 방법 등의 최적화 기법이 적용됩니다.

---

• 최악 시간 복잡도(O(n^2))

최악의 경우, 배열이 이미 정렬되어 있는 경우입니다. 이 경우, 피벗을 어떤 값으로 선택하더라도 배열이 한 쪽으로만 쌓이게 되어 분할이 제대로 이루어지지 않습니다.
이 경우, 시간 복잡도는 O(n^2)이 됩니다.

 

이를 방지하기 위해, 피벗의 선택 방법을 무작위화하는 방법 등의 최적화 기법이 적용됩니다.

 

퀵 정렬의 공간 복잡도는 보조 배열을 생성하는 방법에 따라 달라집니다.

---

• 공간복잡도

 위의 구현 예제에서는 재귀적으로 호출되는 quickSort() 함수마다 새로운 배열을 생성하므로, 공간 복잡도는 O(n log n)입니다. 하지만, 보조 배열을 한 번만 생성하도록 구현할 수 있다면 공간 복잡도를 O(n)으로 줄일 수 있습니다.