[Algorithm]Sort-Quicksort

퀵 정렬은 분할 정복 전략을 사용하여 배열을 정렬하는 가장 인기 있는 정렬 알고리즘 중 하나입니다. 이것은 배열에서 피벗 요소를 선택하고, 피벗을 중심으로 배열을 분할하고, 하위 배열을 재귀적으로 정렬함으로써 작동한다.

그러나 빠른 정렬의 표준 구현은 피벗 요소가 배열에서 가장 작거나 큰 요소일 때 최악의 경우 시간 복잡도가 O(n^2)이다. 이는 대규모 데이터 세트를 정렬할 때 문제가 될 수 있습니다.

이 문제를 해결하기 위해 최악의 경우 O(n log n) 시간 복잡성을 보장하는 "슈퍼" 퀵소트의 수정된 버전을 사용할 수 있다.

슈퍼 퀵소트와 표준 퀵소트의 주요 차이점은 슈퍼 퀵소트가 단순히 첫 번째 요소를 피벗으로 선택하는 대신 세 개의 임의 요소의 중앙값을 피벗 요소로 사용한다는 것이다. 배열의 첫 번째 위치, 중간 위치 및 마지막 위치에서 세 개의 랜덤 요소가 선택됩니다.

function superQuickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  // Select pivot element as median of three random elements
  const pivotIndex = getPivotIndex(arr);
  const pivot = arr[pivotIndex];
  
  // Partition the array around the pivot
  const left = [];
  const right = [];
  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]);
    }
  }
  
  // Recursively sort the sub-arrays
  return [...superQuickSort(left), pivot, ...superQuickSort(right)];
}

function getPivotIndex(arr) {
  const first = arr[0];
  const middle = arr[Math.floor(arr.length / 2)];
  const last = arr[arr.length - 1];
  
  // Return the index of the median of the three random elements
  if (first < middle) {
    if (middle < last) {
      return Math.floor(arr.length / 2);
    } else if (first < last) {
      return arr.length - 1;
    } else {
      return 0;
    }
  } else {
    if (first < last) {
      return 0;
    } else if (middle < last) {
      return Math.floor(arr.length / 2);
    } else {
      return arr.length - 1;
    }
  }
}

이 구현에서는 먼저 배열에 요소가 하나만 있는지 또는 비어 있는지 확인하고, 있으면 배열을 그대로 반환합니다. 그런 다음 getPivotIndex 함수를 사용하여 피벗 요소를 세 개의 임의 요소의 중앙값으로 선택합니다.

그런 다음 왼쪽과 오른쪽의 두 개의 새 배열을 만들고 왼쪽 배열에 피벗보다 작은 요소를 추가하고 오른쪽 배열에 피벗보다 크거나 같은 요소를 추가하여 피벗 요소를 중심으로 배열을 분할합니다.

마지막으로, 왼쪽 및 오른쪽 배열에서 superQuickSort를 호출하고 결과를 피벗 요소와 연결하여 하위 배열을 재귀적으로 정렬한다.

결론적으로, 슈퍼 퀵 정렬은 O(n log n)의 최악의 경우 시간 복잡성을 보장하기 위해 세 개의 임의 요소의 중위수를 피벗 요소로 사용하는 퀵 정렬의 수정이다. 자바스크립트로 구현할 수 있고 대규모 데이터 세트를 정렬하는 데 사용할 수 있는 간단하고 효율적인 알고리즘이다.