please do problem1 - part (c) Note: For this assignment, the word \"comparison\"

Question

please do problem1 - part (c)

Note: For this assignment, the word "comparison" refers only to comparisons involving list elements. For example, if ai and a are list elements in a list of length n, the code if ai aj performs one comparison. Similarly, the code if ai 5 performs one comparison. However, we would say the code if i n performs no comparisons because it is not making a comparison involving a list element. 1. For this problem, consider the following sorting algorithms procedure Sort A(a1, a2,... an: a list of real numbers with n 2 for 2 ton 3. while aj a i:- i 1 6. for k 0 to j -i-1 aj-k F k-1 procedure SortB(a1,az,..., an: a list of real numbers with n 2 1. for j 2 to n 3. while (i> 1 AND aj ai-1) 6. for k 0 to j -i-1 k-1 (a) (2 points) 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 I Comparisons done l Total number of comparisons done so far in this iteration 0th iteratiom 3.25.6.4.1 none iteration 2nd iteration

Explanation / Answer

This is possible because in while loop for A we are checking aj > ai where j>i; where as in B we are checking aj<ai where j>i. so we are getting the result as expected keeping the same invariant of for loop.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.