Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This is a cheatsheet for different selection algorithms for selecting K-th largest or smallest element.
| Selection Algorithms | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Space Complexity | Idea | selecting K-th largest element |
|---|---|---|---|---|---|---|
| QuickSelect | O(n) | O(n) | O(n^2) | O(1) | QuickSelect is an efficient in-place version of QuickSort that only partially sorts the array and returns the desired element. | It selects a pivot element, divides the array into two parts, and recursively repeats the process in the appropriate partition until the K-th largest element is found. |
| Binary Search | O(1) | O(log n) | O(log n) | O(1)->iterative, O(logn)->recursive | It is an efficient algorithm that works on sorted data sets. It uses a divide-and-conquer approach to find the target item in logarithmic time. | Binary search can be applied to an array that is sorted in ascending or descending order to find the K-th largest element. The algorithm repeatedly divides the array into two parts and eliminates the part that does not contain the K-th largest element, until the desired element is found. |
| Median of Medians | O(n) | O(n) | O(n)) | O(logn) | It is an approximate median selection algorithm that helps in creating asymptotically optimal selection algorithms by producing good pivots that improve worst case time complexities for sorting and selection algorithms. | It works by dividing the array into subarrays of size 5, finding the median of each subarray, and recursively finding the median of the medians. The median of the medians serves as the pivot element for the next step of the algorithm. |
| HeapSelect | O(k log n) | O(n + k log n) | O(n log n) | O(n) | HeapSelect is an algorithm for selecting the K-th largest element in an array. It's a variation of the selection problem, which involves finding a specific element in an unordered or partially ordered set. | The array is transformed into a max-heap, and then the root node is repeatedly removed and replaced with the next largest element until the K-th largest element is found. |
| Pick Algorithm | O(5.4305 * n) | O(5.4305 * n) | O(5.4305 * n) | O(5.4305 * n) | Pick operates by successively removing subsets of S whose elements are known to be too small or too large to the iΘS, until only ith of S remains. Each subset removed with contain at least one quarter of the remaining elements. | The PICK method successively eliminates subsets from set S to determine the value of iΘS. By using auxiliary functions b, c, and d, the algorithm ensures that each removed subset contains at least one-quarter of the remaining elements in set S. |
With this cheatsheet at OpenGenus, you must have a strong idea of Selection Algorithms.
