Quick Select | 퀵 선택

퀵 셀렉트는 전체 정렬을 하지 않고 몇번쨰인지만 알고 싶을 때 사용합니다.

[5,2,6,3] 이라는 배열이 있으며 2번쨰로 낮은 순을 알고 싶습니다.

먼저 가장 마지막 요소를 피벗으로 잡습니다.

그리고 left는 가장 왼쪽을 잡고 right는 가장 오른쪽에서 1을 뺸 수로 잡습니다.

그리고 left는 피봇보다 큰 것을 찾습니다.

그리고 right는 피봇보다 작은 것을 작습니다.

찾으면 교환을 합니다.

그리고 다시 찾습니다.

right가 left보다 작거나 같은 순간 [2,5,6]안에서 정렬이 됐다는 걸 의미합니다.

그러면 left와 pivot을 교환합니다.

이러면 3이 올바른 위치에 있게 됩니다.

이때 n번쨰와 비교를 해서 같으면 해당 배열 pivotIndex 값을 반환하면 됩니다.

작으면 다시 재귀로 돌리는데 범위를 left에서 pivot - 1로 하고 크면 pivot + 1, right 사이로 하면 됩니다.

function quickselect(arr, kth, left, right) {
  if (right - left <= 0) {
    return arr[left];
  }
  const pivotIndex = partition(arr, left, right);
  if (kth < pivotIndex) {
    return quickselect(arr, kth, left, pivotIndex - 1);
  } else if (kth > pivotIndex) {
    return quickselect(arr, kth, pivotIndex + 1, right);
  } else {
    return arr[pivotIndex];
  }
}
function partition(arr, left, right) {
  const pivotIndex = right;
  const pivot = arr[pivotIndex];
  right -= 1;
  while (true) {
    while (arr[left] < pivot) {
      left += 1;
    }
    while (arr[right] > pivot) {
      right -= 1;
    }
    if (left >= right) {
      break;
    } else {
      swap(arr, left, right);
    }
  }
  swap(arr, left, pivotIndex);
  return left;
}
// 순서를 바꾸는 함수
function swap(arr, left, right) {
  const temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
}