Consider the Bucket sort algorithm, with the pseudocode below. Which of the foll

Question

Consider the Bucket sort algorithm, with the pseudocode below.

Which of the following is the correct loop invariant for the for loop in lines 7-8?

1. At the start of each iteration i of the for loop, the lists B[1], B[2],..., B[i-1] are sorted.

2. At the start of each iteration i of the for loop, the lists B[0], B[1],..., B[i] are sorted.

3. At the start of each iteration i of the for loop, the lists B[0], B[1],..., B[i-1] are sorted.

BUCKET - SORT(A) 1. let B[O..n 1] be a new array 2. n = A.length 3. for i = 0 to In-1 4. make B[i] an empty list 5. for i = 1 ton 6. insert A[i] into list B[lnAill 7. for i = 0 to n -1 8. sort list B[i] with insertion sort 9. concatenate the lists B[O], B[1], ..., B[n – 1] together in order

Explanation / Answer

3. At the start of each iteration i of the for loop, the lists B[0], B[1],..., B[i-1] are sorted.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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