TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 13.5 - Goodrich, Tamassia, Goldwasser

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

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming