Order Statistics - General (Find the Kth smallest element from an unsorted Array in Linear Time) - Specific ( Find median of unsorted array in Linear Time) - Randomised and Deterministic Algorithms | ISourceCode
Make the frequent cases fast and the rare case correct Order Statistics – General (Find the Kth smallest element from an unsorted Array in Linear Time) – Specific ( Find median of unsorted array in Linear Time) – Randomised and Deterministic Algorithms Given an unsorted array, how quickly can one find the median element? In a simple way we can use a sorting algorithm initially probably a O(n lg n) algorithm and then finding a median or kth smallest element is a trivial matter. Can one do it more quickly than by sorting? This was an open question for some time, solved affirmatively in 1972 by (Manuel) Blum, Floyd, Pratt, Rivest, and Tarjan.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment