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

This chapter provides knowledge of quick sort. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Quick-Sort 3/25/14 15:58 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 Quick-Sort 7 4 9 6 2 → 2 4 6 7 9 4 2 → 2 4 7 9 → 7 9 2→2 © 2014 Goodrich, Tamassia, Goldwasser 9→9 Quick-Sort 1 Quick-Sort ! Quick-sort is a randomized sorting algorithm based on the divide-and-conquer paradigm: n   x Divide: pick a random element x (called pivot) and partition S into w   L elements less than x w   E elements equal x x L E G w   G elements greater than x n   n   Recur: sort L and G Conquer: join L, E and G © 2014 Goodrich, Tamassia, Goldwasser Quick-Sort x 2 1 Quick-Sort 3/25/14 15:58 Partition ! We partition an input sequence as follows: n   n   We remove, in turn, each element y from S and We insert y into L, E or G, depending on the result of the comparison with the pivot x ! Each insertion and removal ! is at the beginning or at the end of a sequence, and hence takes O(1) time Thus, the partition step of quick-sort takes O(n) time © 2014 Goodrich, Tamassia, Goldwasser Algorithm partition(S, p) Input sequence S, position p of pivot Output subsequences L, E, G of the elements of S less than, equal to, or greater than the pivot, resp. L, E, G ← empty sequences x ← (p) while ¬() y ← (()) if y x } (y) return L, E, G Quick-Sort 3 Java Implementation © 2014 Goodrich, Tamassia, Goldwasser Quick-Sort 4 2 Quick-Sort 3/25/14 15:58 Quick-Sort Tree ! An execution of quick-sort is depicted by a binary tree n   Each node represents a recursive call of quick-sort and stores w   Unsorted sequence before the execution and its pivot w   Sorted sequence at the end of the execution n   n   The root is the initial call The leaves are calls on subsequences of size 0 or 1 7 4 9 6 2 → 2 4 6 7 9 4 2 → 2 4 7 9 → 7 9 2→2 9→9 © 2014 Goodrich, Tamassia, Goldwasser Quick-Sort 5 Execution Example ! .

• 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