Javascript에서 Quick Sort

I’m happy to translate the article for you, but I’ll need the full text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the article, I’ll keep the source link at the top unchanged and translate the rest into Korean while preserving all formatting, markdown, and code blocks.

개요

퀵 정렬은 널리 사용되는, 빠르고 우아한 분할‑정복 정렬 알고리즘입니다.
기본 아이디어:

1. 피벗 요소를 선택합니다.
2. 배열을 분할하여 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동시킵니다.
3. 왼쪽과 오른쪽 하위 배열에 동일한 논리를 재귀적으로 적용합니다.

“퀵 정렬은 매 단계마다 문제 크기를 크게 줄이기 때문에 빠릅니다.”

함수형 (제자리 연산이 아닌) 퀵 정렬

// functional quick sort
const quickSort = (arr) => {
  if (arr.length  {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j  {
  if (low  {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i]  pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const hoarePartition = (arr, low, high) => {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const quickSortHoare = (arr, low = 0, high = arr.length - 1) => {
  if (low < high) {
    const p = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, p);
    quickSortHoare(arr, p + 1, high);
  }
  return arr;
};

예시

전: [34, 56, 3, 234, 6, 7] (피벗 = 34)
분할 후: [7, 6, 3 | 234, 56, 34] – 분할 인덱스 = 2를 반환합니다.

Lomuto와의 주요 차이점

• 피벗이 반드시 최종 정렬 위치에 놓이는 것은 아닙니다.
• 함수는 피벗 인덱스가 아니라 경계 인덱스를 반환합니다.
• 교환 횟수가 적어 일반적으로 더 빠르며, 특히 중복이 많은 경우에 유리합니다.

비교: Lomuto vs. Hoare

복잡도 분석

• 공간 복잡도
  • 함수형 퀵 정렬: O(n) (추가 배열).
  • 제자리 퀵 정렬: O(log n) (재귀 스택).

요약

• Functional Quick Sort는 이해하기 쉽지만 추가 메모리를 사용합니다.
• In‑place Quick Sort는 Lomuto 또는 Hoare 파티셔닝을 사용하며, 실제 코드에 선호됩니다.
• Hoare’s scheme은 일반적으로 교환 횟수가 적고 중복 값이 있을 때 성능이 좋으며, Lomuto’s scheme은 더 간단하고 피벗이 최종 위치에 놓인다는 것을 보장합니다.

환경의 제약과 정렬하려는 데이터의 특성에 가장 잘 맞는 버전을 선택하십시오.