Quick select

quick-select.md

Problem - Find the kth smallest/largest number in an unsorted array with n element.

Explanation: https://www.youtube.com/watch?v=hGK_5n81drs&ab_channel=BackToBackSWE

Quick select approach: The way that this is done is by using a form of quick sort. It work by a way of partitioning the array into parts.

Lets say we want to find the kth largest number in an array. If the array was sorted we would know what the index of this number would be, it would be (n - k). Since the array isn't sorted we need to find element for the index (n - k).

Now, to find the element we need to implement quick select. Quick select work like this (for finding the largest K):

• First we break the algorithm down to a partition and a selection function.

• The partition function uses the Lomuto algorithm, which finds the real index of a pivot element and sorts the array such that:

  • every element on the left side of the real index of a pivot is smaller than the pivot element
  • every element on the right side of the real index of a pivot is larger than the pivot element

  const partition = (array: number[], lowIndex: number = 0, highIndex: number = array.length - 1) => {
      // We are trying to find a candidate to be the index of the pivot.
      let i = lowIndex; // At the end, (i) will be the real index of the pivot. 
      let j = lowIndex;
      let pivot = array[highIndex];
      while(j < highIndex) {
          if(array[j] < pivot) {
              // This guarantees that all the values on left and the right of the pivot real index are smaller and greater than the pivot respectively.
              swap(array, i, j);
              i++;
          }
          j++;
      }
      swap(array, i, highIndex); // (i) is the real index of the pivot, so we swap the pivot element to its rightfull position.
      return i;
  }

  • This partition function will have:
    • Worst case: O(n)

• The selection function is straightforward, we keep track of the low and high indexes which represents the partitions of the array. While the low is different than the high, meaning that there is more than two element in the array, we run the partition function to partition the current partition. It will return the pivotIndex, so we check if the index returned is the desired index (n - k). If it is not we need to choose the next partition to evaluate, either the left or the right, since we known the desired index, we need to choose the partition that contains the desired index. This is simply done by updating the current partition variables (low and high). Since we might have a partition that contains only one element, we exit the loop and check if the element index is the desired index. If so we return the element. Otherwise there is no solution, the k > array.length.

  const quickSelectKthLargest = (array: number[], k: number): number => {
      const desiredIndex = array.length - k;
      let low = 0;
      let high = array.length - 1;
      while(low !== high) {
          let pivotIndex = partition(array, low, high);
          if(pivotIndex === desiredIndex) {
              return array[pivotIndex];
          } else if (pivotIndex < desiredIndex) {
              low = pivotIndex + 1;
          } else {
              high = pivotIndex - 1;
          }
      }
      if(low === desiredIndex) {
          return array[low]; // We have chosen the side that only has one element, it must be in the desired index.
      }
      throw Error('No solution!');
  }

  • This selection function will have:
    • Worst case: O(n) * O(n) = O(n^2)
    • Average case: O(n)