1. This problem refers to the following two algorithms. procedure Sort (a1,a2, ,
ID: 3813842 • Letter: 1
Question
1. This problem refers to the following two algorithms. procedure Sort (a1,a2, ,an: a list of real numbers with n 1) 1. for i 1 to n -1 2. item. 3. location. i 4. for j i-- 1 to m if aj item then item. location alocation item procedure SortB(a1, a2,..., an: a list of real numbers with n 1 1. for k 1 to n -1 3. item. 4. location. i 5. for j 1 to i 1 if aj item then item. location 9. alocation :a ai 10. ai item (a) Trace the behavior of SortA on the input list 4,2,5, 6, 1,3 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 tal number of in this iteration comparisons done so far 0th iteration 4,2, 5, 6, 1,3 1st iteration. 2nd iteration.Explanation / Answer
sortA:
list comarisons total comarisons
0th iteration: 4 2 5 6 1 3 0 0
1st iteration: 1 2 5 3 4 6 5 5 swapping 4 and 1
2nd iteration: 1 2 5 3 4 6 4 9 swapping 2 and 2
3rd iteration: 1 2 3 5 4 6 3 12 swapping 5 and 3
4th iteration: 1 2 3 4 5 6 2 14 swapping 5 and 4
5th iteration: 1 2 3 4 5 6 1 15 swapping 5 and 5
sortB:
list comarisons total comarisons
0th iteration: 4 2 5 6 1 3 0 0
1st iteration: 4 2 5 3 1 6 5 5 swapping 6 and 3
2nd iteration: 4 2 1 3 5 6 4 9 swapping 5 and 1
3rd iteration: 3 2 1 4 5 6 3 12 swapping 3 and 4
4th iteration: 1 2 3 4 5 6 2 14 swapping 3 and 1
5th iteration: 1 2 3 4 5 6 1 15 swapping 1 and 1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.