Quick Select

빠른 선택

• 정렬되지 않는 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘
• 빠른 정렬 알고리즘과 같은 접근법을 사용
• 기준점을 선택한 다음 배열을 분할, 하지만 빠른 정렬처럼 기준점의 양쪽 모두를 재귀적으로 수행하는 대신 한쪽만을 재귀적으로 수행
• 복잡도 O(Nlog2(N)) -> O(N)으로 낮아짐

코드 구현

const partition = (array, left, right) => {
  let pivot = array[Math.floor((right+left)/2)];
  
  while(left <= right) {
    while(pivot > array[left]) {
      left++;
    }
    
    while(pivot < array[right]) {
      right--;
    }
    
    if(left <= right) {
      [array[left],array[right]] = [array[right], array[left]];
      left++;
      right--;
    }
  }
  return left;
}

const quickSelectInPlace = (A, l, h, k) => {
  let p = partition(A, l, h);
  
  if(p === (k-1)) {
    return A[p];
  } else if(p>(k-1)) {
    return quickSelectInPlace(A, l, p-1, k);
  } else {
    return quickSelectInPlace(A, p+1, h, k);
  }
}

let array = [1,2,3,-2,3,14,7,8,1,2,2];
quickSelectInPlace(array, 0, array.length-1, 5); // 2
quickSelectInPlace(array, 0, array.length-1, 10); // 8

// 중간값 구하는 함수
const medianQuickselect = array => {
  return quickSelectInPlace(array, 0, array.length-1, Math.floor(array.length/2));
}