W2_L_2_HS2023.pdf

FTP Alg Week2 [email protected] HS2023 1/28 Sorting algorithms Sorting is considered the most fundamental problem in the study of algorithms: ▶ Sorting is often a tool for other applications. Often, in order to apply some algorithm, one has t...

FTP Alg Week2 [email protected] HS2023 1/28 Sorting algorithms Sorting is considered the most fundamental problem in the study of algorithms: ▶ Sorting is often a tool for other applications. Often, in order to apply some algorithm, one has to order some objects. ▶ Many different techniques have been developed for solving different sorting problems. ▶ We have seen insertion–sort. The running time is Θ(n2 ) in the worst case. It is a fast in-place algorithm for sorting problem with small n. ▶ We will consider merge sort, heapsort (and quicksort later). ▶ We will see that merge sort has a better running time than insertion-sort. 2/28 How to improve the complexity? We present a recursive structure based on divide–and–conquer. Divide the problem in sub–problems of smaller size. Conquer the sub-problems, i.e. solve them (usually with a recursive method). Combine the solutions of the sub–problems into a solution for the original whole problem. An example of the above procedure is the merge sort algorithm, which operates as follows: Divide: Divide the sequence of n numbers into two sub–sequences of (about) n/2 elements each. Conquer: Sort the each sub–sequence recursively using the merge sort. Combine: Merge the two above outputs to produce the sorted sequence. 3/28 Recursive functions ▶ As you can see in previous slide, we defined merge sort procedure by using merge sort. This can be viewed as a recursive procedure or recursive function. ▶ A typical example of recursive function is related to the Fibonacci numbers: they are a sequence of numbers {fn }n≥0 defined by ( f0 = 0, f1 = 1 fn = fn−1 + fn−2 for all n ≥ 2 The first elements are the following ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,... 4/28 Recursive functions: Examples https://www.youtube.com/watch?v=BalWjeY2O9g https://www.youtube.com/watch?v=b005iHf8Z3g 5/28 Merge procedure ▶ In Merge–sort we call the auxiliary procedure MERGE(A, p, q, r ), where A is an array, p ≤ q < r are indexes into the array. ▶ In the procedure the sub–arrays A[p,... , q] and A[q + 1,... , r ] are already sorted. The call MERGE(A, p, q, r ) merges the above two sub–arrays into a single sorted sub–array. ▶ In the next slide we show the pseudo–code of merge procedure. We use two sentinels, that are cards denoted by ∞, which determine the bottom of the pile’s. This trick simplifies the code. 6/28 Merge: Pseudo–code ▶ L1–L2: the length of the sub–arrays are determined. ▶ L3: new arrays are created of length n1 + 1 and n2 + 1 resp. ▶ L4–L9: we copy the old array in the next ones L and R where we add the sentinels. ▶ L10–11: loop initialization ▶ L12–17, merges the two sub–arrays as illustrated in the next figure. 7/28 Merge Infinity in order to finish the algorithm at some point At the start of each loop we have A[p,... , k − 1] containing in a sorted order all k − p smallest elements of L[1,... , n1 + 1] and R[1,... , n1 + 1] and L[i] and R[j] are the smallest element of the two sub–arrays, which have not been copied back into A. 8/28 Merge 9/28 Merge: running time Let n = r − p + 1. For analyzing the running time of merge, observe that: ▶ Lines 1–3 and 8–1 take constant time. ▶ The two for loops in 4-7 both require O(n) operations, that should be added up. ▶ Finally there is n iteration of the loop at lines 12–17, each of which takes constant time. Thus the running time is Θ(n). 10/28 Merge-sort - As we have seen in a previous slide, MERGE is a sub–routine in the merge sort algorithm. - Let p < r be non negative integers. MERGE–SORT(A,p,r) sorts the elements of the array A[p,... , r ]. - If this array has more that one element, the first step of the procedure is to divide into two sub–arrays A[p,... , q] and A[q + 1,... , r ], where q = ⌊n/2⌋. To sort the entire sequence A =< A, A,... , A[n] >, where n = A.length, we make the call MERGE–SORT(A, 1, A.length). 11/28 Merge–Sort: Example Next figure shows an example of iterations of MERGE–SORT. 12/28 Merge-sort: Analyzing divide-and-conquer algorithms 1. MERGE–SORT is a divide–and–conquer algorithm. 2. Let us denote by T (n) be the running time of an algorithm for a size n elements. 3. If the problem size is small enough, say n ≤ c for a constant c, the solution take Θ(1) time. (For merge sort c = 1) 4. Suppose that the algorithm divide the problem in a sub–problems, each with size 1/b of the original one (for merge sort a = b = 2). 5. Let D(n) be the time for dividing in sub–problems and C (n) be the time for combining together the solutions of the sub–problems. 6. We get the recurrence: ( Θ(1) if n ≤ c T (n) = aT (n/b) + D(n) + C (n) otherwise 13/28  Master Theorem is not universal Master Theorem Let a ≥ 1, b > 1 be constants, f (n) be a function and T (n) defined by the following recurrence T (n) = aT (n/b) + f (n). where n/b is interpreted as either ⌊n/b⌋ or ⌈n/b⌉. Then 1. T (n) = Θ nlogb a if f (n) = O nlogb a−ϵ for some ϵ > 0.

2. T (n) = Θ nlogb a ln n if f (n) = Θ nlogb a.

3. T (n) = Θ (f (n)) if f (n) = Ω nlogb a+ϵ for some ϵ > 0, and if
af (n/b) ≤ c · f (n) for all n ≥ n0 , where c and n0 are positive constant with c < 1. In merge sort a = b = 2 and f (n) = D(n) + C (n) = Θ(n). Thus the running time is Θ(n log n). 14/28 Heapsort - We have seen insertion sort and merge sort. We present heapsort that mixes the advantages of the previous two algorithms. - Insertion sort operates in place with running time O(n2 ). - Merge sort has running time O(n log n), but it does not sort in place. - Heapsort has running time O(n log n) and sorts in place. - The (binary) heap data structure is stored in an array, but it is used like a (binary) tree. - An array representing a heap has two attributes: A.length, which is the number of the element in the array, and A.heap.size, which is the number of elements that are stored in the heap. 15/28 Heapsort The tree is complete at each level, except possibly the lowest, which is filled from the left. ▶ In (a) we have a tree representing a max–heap (we give the definition in the next slide); the nodes contain the stored objects and above each node there is the corresponding index. ▶ In (b) we have the corresponding array. 16/28 Heaps construction The root is A. A parent node can have two children, a left and a right one. PARENT(i) returns ⌊i/2⌋. If a node i has two children, LEFT(i) returns 2i, RIGHT(i) returns 2i + 1 There are two types of heaps: max-heaps and min-heaps. ▶ For max–heap, the following property is true: A[Parent(i)] ≥ A[i] ▶ For min–heap, the following property is true: A[Parent(i)] ≤ A[i] For the heapsort algorithm we use a max–heap. 17/28 Heap functions - MAX-HEAPIFY procedure maintains the max–heap property. It has running time O(log n) - BUILD-MAX-HEAP procedure creates a max–heap from an non-ordered input array. It runs in O(n) time. - HEAPSORT procedure sorts an array in place with a running time O(n log n). 18/28 MAX–HEAPIFY The Input of MAX–HEAPIFY is an array A and an index i of the array, where we assume that the binary trees with roots LEFT(i) and RIGHT(i) are max–heaps and A[i] may be smaller of its children. At each step the largest of the elements A[i], A[LEFT(i)] and A[RIGHT(i)] is determined and its index becomes the largest. In case the largest is one of the child, parent and largest child are permuted. Then we iterate the process to the sub–tree with the new root. 19/28 MAX–HEAPIFY: Example The figure below shows max-heaps, obtained with the MAX–HEAPIFY procedure. 20/28 MAX–HEAPIFY: Running time - Let n be the size of the sub–tree with root i to which we call MAX–HEAPIFY. - The first step is to fix up the relationship among the elements on i and its children. This takes Θ(1) time. - Then, if needed (in the worst case), we iterate the MAX–HEAPIFY to the tree with root the largest child of i. - A children subtree has size at most 2n/3. Thus T (n) ≤ T (2n/3) + Θ(1) (equality is the worst case) - Master Theorem tells us that MAX–HEAPIFY has running time O(ln n). 21/28 BUILD-MAX-HEAP It converts an array A[1,... , n] into a max–heap. The nodes in A[⌊n/2⌋ + 1,... , n] are leaves (i.e. do not have any children). We call MAX–HEAPIFY for all nodes except the ones in the last level of the tree (the one with only leaves). One can see that the loop invariant holds at each step. The running time is O(n) (the proof can be read on the book). 22/28 BUILD-MAX-HEAP: Example 23/28 Heapsort The goal is to sort (in increasing order) an array A[1,... , n]. The algorithm starts with the call of BUILD–MAX–HEAP. Therefore A is a max of the elements in A. Lines 2 and 3 (in the first loop) exchange A[n] with A. Line 4 excludes A[n] form the heap. Line 5 create a new Max-Heap without A[n] The loops continue with final point n − 1 and so on. The running time is O(n log n), because BUILD–MAX–HEAP takes O(n) and each of the n − 1 calls to MAX–HEAPIFY takes O(log n). 24/28 Heapsort: Example The example start after the call BUIL–MAX–HEAP: 25/28 Heapsort: conclusion - It sorts in-place, i.e. does not require a separate array. - Excellent complexity O(n log n), compared to the O(n2 ) of the insertion sort and others. - However, a good implemention of quicksort is usually faster, even though they have same average complexity O(n log n). - We will see it in the next chapter on randomized algorithms. 26/28 Sorting algorithms complexity n denotes the number of object to sort. For counting sort, the items are integers in {0, 1... , k}. In Radix the number have d–digits 27/28 References: The material contained in these slides is taken form the book “Introduction to Algorithms: third edition”: Section 2.3.1, Section 2.3.2, Section 4.5, Section 6.1, Section 6.2, Section 6.3, Section 6.4. 28/28