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

This chapter provides knowledge of merge sort. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Merge Sort 3/25/14 15:46 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 Merge Sort 7 2 ⏐ 9 4 → 2 4 7 9 7 ⏐ 2 → 2 7 7→7 © 2014 Goodrich, Tamassia, Goldwasser 9 ⏐ 4 → 4 9 2→2 9→9 4→4 Merge Sort 1 Divide-and-Conquer ! Divide-and conquer is a ! Merge-sort is a sorting general algorithm design paradigm: n   n   n   Divide: divide the input data S in two disjoint subsets S1 and S2 Recur: solve the subproblems associated with S1 and S2 Conquer: combine the solutions for S1 and S2 into a solution for S ! The base case for the recursion are subproblems of size 0 or 1 © 2014 Goodrich, Tamassia, Goldwasser Merge Sort ! algorithm based on the divide-and-conquer paradigm Like heap-sort n   It has O(n log n) running time ! Unlike heap-sort n   n   It does not use an auxiliary priority queue It accesses data in a sequential manner (suitable to sort data on a disk) 2 1 Merge Sort 3/25/14 15:46 Merge-Sort ! Merge-sort on an input sequence S with n elements consists of three steps: n   n   n   Divide: partition S into two sequences S1 and S2 of about n/2 elements each Recur: recursively sort S1 and S2 Conquer: merge S1 and S2 into a unique sorted sequence © 2014 Goodrich, Tamassia, Goldwasser Algorithm mergeSort(S) Input sequence S with n elements Output sequence S sorted according to C if () > 1 (S1, S2) ← partition(S, n/2) mergeSort(S1) mergeSort(S2) S ← merge(S1, S2) Merge Sort 3 Merging Two Sorted Sequences ! The conquer step of ! merge-sort consists of merging two sorted sequences A and B into a sorted sequence S containing the union of the elements of A and B Merging two sorted sequences, each with n/2 elements and implemented by means of a doubly linked list, takes O(n) time © 2014 Goodrich, Tamassia, Goldwasser Algorithm merge(A, B) Input sequences A and B with n/2 elements each Output sorted sequence of A ∪ B S ←

• 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