算法分析代写 | CSE 21 HW 3

这个作业是对排序算法进行分析比较
CSE 21 HW 3

(1) Consider the following two algorithms.
procedure SortA(a1, a2, . . . , an: a list of real numbers with n ≥ 2)
(a) for j := 2 to n
(b) i := 1
(c) while aj > ai
(d) i := i + 1
(e) m := aj
(f) for k := 0 to j − i − 1
(g) aj−k := aj−k−1
(h) ai
:= m
procedure SortB(a1, a2, . . . , an: a list of real numbers with n ≥ 2)
1. for j := 2 to n
2. i := j
3. while (i > 1 AND aj < ai−1) 4. i := i − 1 5. m := aj 6. for k := 0 to j − i − 1 7. aj−k := aj−k−1 8. ai := m (a) Trace the behavior of SortA on the input list 3, 2, 5, 6, 4, 1 by filling in the following table. Each row corresponds to the completion of one iteration of the outermost loop. When listing the comparisons done in each iteration, say which two elements are being compared in each comparison (example: 3 vs. 5). After the… What the list looks like Comparisons done Total number of in this iteration comparisons done so far 0th iteration 3, 2, 5, 6, 4, 1 none 0 1st iteration 2nd iteration . . . (b) Trace the behavior of SortB on the input list 3, 2, 5, 6, 4, 1 by filling in the following table. Each row corresponds to the completion of one iteration of the outermost loop. When listing the comparisons done in each iteration, say which two elements are being compared in each comparison (example: 3 vs. 5). After the… What the list looks like Comparisons done Total number of in this iteration comparisons done so far 0th iteration 3, 2, 5, 6, 4, 1 none 0 1st iteration 2nd iteration . . . 1 2 Note: For parts (c)-(f), the input elements are distinct. (c) Find (with explanation) an input list containing the numbers 1, 2, 3, 4, 5, and 6 for which SortA does the fewest possible number of comparisons (i.e. a best-case input). (d) Find (with explanation) an input list containing the numbers 1, 2, 3, 4, 5, and 6 for which SortB does the fewest possible number of comparisons (i.e. a best-case input). (e) Find (with explanation) an input list containing the numbers 1, 2, 3, 4, 5, and 6 for which SortA does the greatest possible number of comparisons (i.e. a worst-case input). (f) Find (with explanation) an input list containing the numbers 1, 2, 3, 4, 5, and 6 for which SortB does the greatest possible number of comparisons (i.e. a worst-case input). (g) For the input list 1, 2, 3, . . . , n − 1, n (when the input happens to be already sorted), how many comparisons does SortA perform, in terms of n? Simplify your answer. (h) For the input list 1, 2, 3, . . . , n − 1, n (when the input happens to be already sorted), how many comparisons does SortB perform, in terms of n? Simplify your answer. (2) The following algorithm has access to a global list of distinct integers a1, a2, . . . , an. When called with parameters i, j, x, Search(i, j, x) returns the location of the target value x among {ai , . . . , aj}, or 0 if the target value is not present in {ai , . . . , aj}. procedure Search(i, j, x : i, j, x integers, 1 ≤ i ≤ j ≤ n) 1. if ai = x then 2. return i 3. else if i = j then 4. return 0 5. else 6. return Search(i + 1, j, x) Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Then solve the recurrence and write the solution in big-Θ notation.