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

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.

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。