TAILIEUCHUNG - Lecture Algorithms and data structures: Chapter 7 - Merge Sort
In this topic, we will look at: Justification for analysis, quadratic and polynomial growth, counting machine instructions, Landau symbols, Big-Q as an equivalence relation, little-o as a weak ordering. | Review 1 Quick Sort Quick Sort Algorithm Time Complexity Best case Average case Worst case Examples Quick Sort Example 2 Merge Sort 3 Merge Sort Merge Sort Algorithm Time Complexity Best case Average case Worst case Examples Introduction Merging is the process of combining two or more sorted array into a third sorted array Apply divide-and-conquer to sorting problem Divide the array into approximately n/2 sub-arrays of size two and sort the elements in each sub array Merging each sub-array with the adjacent sub-array will get another sorted sub-array Repeat this process until there is only one array remaining of size n Since at any time the two arrays being merged are both sub-arrays of A, lower and upper bounds are required to indicate the sub-arrays being merged 4 Let A be an array of n number of elements to be sorted A[1], A[2] A[n] Step 1: Divide the array A into approximately n/2 sorted sub-array, ., the elements in the (A [1], A [2]), (A [3], A [4]), (A [k], A [k + 1]), (A [n – 1], A [n]) sub-arrays are in sorted order Step 2: Merge each pair of pairs to obtain the following list of sorted sub-array The elements in the sub-array are also in the sorted order (A [1], A [2], A [3], A [4)), (A [k – 1], A [k], A [k + 1], A [k + 2]), (A [n – 3], A [n – 2], A [n – 1], A [n]). Step 3: Repeat the step 2 recursively until there is only one sorted array of size n 5 Example To illustrate the merge sort algorithm consider the following array with 7 elements [42], [33], [23], [74], [44], [67], [49] 6 cont 7 Merging The key to Merge Sort is merging two sorted lists into one, such that if you have two lists X (x1 x2 xm) and Y(y1 y2 yn) the resulting list is Z(z1 z2 zm+n) Example: L1 = { 3 8 9 } L2 = { 1 5 7 } merge(L1, L2) = { 1 3 5 7 8 9 } 8 Merging (cont.) 3 10 23 54 1 5 25 75 X: Y: Result: 9 Merging (cont.) 3 10 23 54 5 25 75 1 X: Y: Result: 10 Merging (cont.) 10 23 54 5 25 75 1 3 X: Y: Result: 11 Merging (cont.) 10 23 54 25 75 1 3 5 X: Y: .
đang nạp các trang xem trước
