Quickselect

Memorize

To be memorize and the analysis.

QuickSelect is an algorithm for finding the kth smallest element in an unsorted array. Searching Algorithms It uses the partition function to rearrange the elements and recursively narrows down the search range based on the position of the pivot.

Quickselect and Quick Sort rely on two subroutines:

• choose-pivot(A)
  • Simplest idea: Always select rightmost element in array
• partition(A, p) Partition Algorithm $O(n)$
  • Rearrange A and return pivot-index $i$ so that
    • the pivot-value $v$ is in $A[i]$
    • all items in $A[0,...,i-1]$ are $\le v$
    • all items in $A[i+1,...,n+1]$ are $\ge v$

The Algorithm of Quick Select

Pseudocode:

QuickSelect(A, k)
A: array of size n, k: integer such that 0 ≤ k < n
 
1. p ← choose-pivot(A)  // Choose a pivot element
2. i ← partition(A, p)  // Partition the array around the pivot
3. if i = k then
     return A[i]  // Found the k-th smallest element
4. else if i > k then
     return QuickSelect(A[0, 1, ..., i-1], k)  // Search in the left partition
5. else if i < k then
     return QuickSelect(A[i+1, i+2, ..., n-1], k - (i+1))  // Search in the right partition

• In this algorithm, we start by choosing a pivot element p from the array A. Then, we call the partition function to partition the array around the pivot. The partition function rearranges the elements such that all elements smaller than the pivot are placed before it, and all elements greater than the pivot are placed after it. It also returns the index i where the pivot ends up after partitioning.
• After partitioning, we check if the index i is equal to k. If it is, we have found the kth smallest element and return it. If i is greater than k, it means the kth smallest element is in the left partition, so we recursively call QuickSelect on the left partition of the array. If i is less than k, it means the kth smallest element is in the right partition, so we recursively call QuickSelect on the right partition of the array, adjusting k accordingly.
• The algorithm continues recursively narrowing down the search range until the kth smallest element is found.

Analysis of Quick Select:

Best Case: $\Theta (n)$ Worst Case: $\Theta (n^2)$

Average case:

• $\Theta (n\log n)$?