COS 226 Midterm: COS 226 Princeton Midterm Fall 12 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
2-0 1-8 7-9 0-9 8-5 4-1 1-9 3-8 5-6: eight sorting algorithms. 0 2 9 7 6 8 5 4 3 1: analysis of algorithms. (a) n 2. Each of the n bs must be compared and exchanged with each of the n as. (b) 3n. After the rst partition, all of the keys equal to the partitioning item (either all of the as or all of the bs) will be nished. The second (and nal) partition will complete the sort using n compares: 3-heaps. Here is a drawing of the original 3-heap: 1 (a) to delete-the-maximum, we exchange 88 with 7 and sink 7 down. To sink 7 down, we exchange 7 with its largest child (77) and then again exchange 7 with its largest child (75). 15 (b) 3k 1, 3k, 3k + 1 (c) 3 log3 n. To sink a key, we repeatedly exchange it with its largest child (if the is less than the largest child).
