Blum Floyd Pratt Rivest Tarjan Algorithm
Algorithm to find kth largest element from an unsorted array in linear time. Algorithm If the number of elements in an array is large .Divide the array into arrays each with 5 elements ⇨ n/5 arrays. Compute Median of all arrays of 5 elements. This can be done by sorting each group and taking middle element. This results in time complexity of n/5 * 5log5. (Sorting each group takes 5log5, and we have n/5 arrays) All the computed medians from each sub-array are then collected into a new, smaller array. Now, compute median of this array Use this Median as Pivot in QuickSelect Median > half of these n/5 group medians. So median > n/10 medians. ...