randomized quick-select in applying the prune-and-search pattern to finding the kth smallest element in an unordered sequence of elementswe describe simple and practical algorithmknown as randomized quick-select this algorithm runs in (nexpected timetaken over all possible random choices made by the algorithmthis expectation does not depend whatsoever on any randomness assumptions about the input distribution we note though that randomized quick-select runs in ( time in the worst casethe justification of which is left as an exercise ( - we also provide an exercise ( - for modifying randomized quick-select to define deterministic selection algorithm that runs in (nworst-case time the existence of this deterministic algorithm is mostly of theoretical interesthoweversince the constant factor hidden by the big-oh notation is relatively large in that case suppose we are given an unsorted sequence of comparable elements together with an integer [ nat high levelthe quick-select algorithm for finding the kth smallest element in is similar to the randomized quick-sort algorithm described in section we pick "pivotelement from at random and use this to subdivide into three subsequences leand gstoring the elements of less thanequal toand greater than the pivotrespectively in the prune stepwe determine which of these subsets contains the desired elementbased on the value of and the sizes of those subsets we then recur on the appropriate subsetnoting that the desired element' rank in the subset may differ from its rank in the full set an implementation of randomized quick-select is shown in code fragment def quick select(sk) """return the kth smallest element of list sfor from to len( "" if len( = return [ pivot random choice(spick random pivot element from [ for in if pivotelements less than pivot [ for in if =pivotelements equal to pivot [ for in if pivot xelements greater than pivot if <len( )kth smallest lies in return quick select(lk elif <len(llen( ) return pivot kth smallest equal to pivot else len(llen(enew selection parameter kth smallest is jth in return quick select(gjcode fragment randomized quick-select algorithm