This chapter provides knowledge of selection. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Selection 3/29/14 21:22 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Selection © 2014 Goodrich, Tamassia, Goldwasser Selection 1 The Selection Problem ! Given an integer k and n elements x1, x2, , xn, taken from a total order, find the k-th smallest element in this set. ! Of course, we can sort the set in O(n log n) time and then index the k-th element. k=3 7 4 9 6 2 → 2 4 6 7 9 ! Can we solve the selection problem faster? © 2014 Goodrich, Tamassia, Goldwasser Selection 2 1 Selection 3/29/14 21:22 Quick-Select ! Quick-select is a randomized selection algorithm based on the prune-and-search paradigm: n x Prune: pick a random element x (called pivot) and partition S into x w L: elements less than x w E: elements equal x L w G: elements greater than x n Search: depending on k, either answer is in E, or we need to recur in either L or G © 2014 Goodrich, Tamassia, Goldwasser Selection E k |L|+|E| k’ = k - |L| - |E| |L| x } (y) return L, E, G Selection 4 2 Selection 3/29/14 21:22 Quick-Select Visualization ! An execution of quick-select can be visualized by a recursion path n Each node represents a recursive call of quick-select, and stores k and the remaining sequence k=5, S=(7 4 9 3 2 6 5 1 8) k=2, S=(7 4 9 6 5 8) k=2, S=(7 4 6 5) k=1, S=(7 6 5) 5 © 2014 Goodrich, Tamassia, Goldwasser Selection 5 Expected Running Time ! Consider a recursive call of quick-select on a sequence of size s n n Good call: the sizes of L and G are each less than 3s/4 Bad call: one of L and G has size greater than 3s/4 7 2 9 43 7 6 1 7 2 9 43 7 6 19 2 4 3 1 7 9 7 1 → 1 1 7294376 Good call Bad call ! A call is good with probability 1/2 n 1/2 of the possible pivots cause good calls: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Bad pivots © 2014 Goodrich, Tamassia, Goldwasser Good pivots Selection Bad .
