quick select

정의

• 평균 시간 복잡도: O(n)

• 최악 시간 복잡도: O(n²)

• 공간 복잡도: O(1) in-place

핵심 전략

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

var findKthLargest = function (nums, k) {
    const targetIdx = nums.length - k;
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const randomPivotIndex = left + Math.floor(Math.random() * (right - left + 1));
        swap(nums, left, randomPivotIndex);
        const pivot = nums[left];
        
        // 3-way partition을 위한 포인터 설정
        // lt: 피벗보다 작은 그룹의 오른쪽 경계
        // gt: 피벗보다 큰 그룹의 왼쪽 경계
        // i: 현재 탐색중인 인덱스
        let lt = left;
        let gt = right;
        let i = left + 1;

        while (i <= gt) {
            if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
                i++;
            } else if (nums[i] > pivot) {
                swap(nums, i, gt);
                gt--;
            } else { // nums[i] === pivot
                i++;
            }
        }
        
        swap(nums, left, lt);

        if (targetIdx < lt) {
            right = lt - 1;
        } else if (targetIdx > gt) {
            left = gt + 1;
        } else {
            return pivot;
        }
    }
};

구현1 - 마지막 요소 pivot & 큰 값

// partition 함수: pivot을 기준으로 배열을 나누고 최종 pivot 위치 반환
function partition(arr, left, right) {
  const pivotValue = arr[right]; // 항상 마지막 요소를 pivot으로 선택
  let storeIndex = left;

  for (let i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      [arr[i], arr[storeIndex]] = [arr[storeIndex], arr[i]];
      storeIndex++;
    }
  }

  // pivot을 제자리로 옮김
  [arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
  return storeIndex;
}

// Quick Select 메인 함수 (k번째 큰 값)
function findKthLargest(arr, k) {
  const targetIndex = arr.length - k; // k번째 큰 값 → (n-k)번째 작은 값

  function select(left, right, targetIndex) {
    if (left === right) return arr[left];

    const pivotIndex = partition(arr, left, right);

    if (targetIndex === pivotIndex) {
      return arr[pivotIndex];
    } else if (targetIndex < pivotIndex) {
      return select(left, pivotIndex - 1, targetIndex);
    } else {
      return select(pivotIndex + 1, right, targetIndex);
    }
  }

  return select(0, arr.length - 1, targetIndex);
}

구현2 - 마지막 요소 pivot & 작은 값

// partition 함수: pivot을 기준으로 배열을 나누고 최종 pivot 위치 반환
function partition(arr, left, right) {
  const pivotValue = arr[right]; // 항상 마지막 요소를 pivot으로 선택
  let storeIndex = left;

  for (let i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      [arr[i], arr[storeIndex]] = [arr[storeIndex], arr[i]];
      storeIndex++;
    }
  }

  // pivot을 제자리로 옮김
  [arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
  return storeIndex;
}

// Quick Select 메인 함수
function quickSelect(arr, k) {
  function select(left, right, kSmallest) {
    if (left === right) return arr[left];

    // pivot을 항상 마지막 요소로 선택
    const pivotIndex = partition(arr, left, right);

    if (kSmallest === pivotIndex) {
      return arr[kSmallest];
    } else if (kSmallest < pivotIndex) {
      return select(left, pivotIndex - 1, kSmallest);
    } else {
      return select(pivotIndex + 1, right, kSmallest);
    }
  }

  return select(0, arr.length - 1, k);
}

구현3 - 작은 값 & 랜덤 값 pivot

// partition 함수: pivot을 기준으로 배열을 나누고 최종 pivot 위치 반환
function partition(arr, left, right, pivotIndex) {
  const pivotValue = arr[pivotIndex];

  // pivot을 끝으로 보냄
  [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];

  let storeIndex = left;
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      [arr[i], arr[storeIndex]] = [arr[storeIndex], arr[i]];
      storeIndex++;
    }
  }

  // pivot을 제자리로 옮김
  [arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
  return storeIndex;
}

// Quick Select 메인 함수
function quickSelect(arr, k) {
  function select(left, right, kSmallest) {
    if (left === right) return arr[left];

    // pivot을 랜덤으로 선택
    let pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;

    pivotIndex = partition(arr, left, right, pivotIndex);

    if (kSmallest === pivotIndex) {
      return arr[kSmallest];
    } else if (kSmallest < pivotIndex) {
      return select(left, pivotIndex - 1, kSmallest);
    } else {
      return select(pivotIndex + 1, right, kSmallest);
    }
  }

  return select(0, arr.length - 1, k);
}