Consider the Bucket sort algorithm with the pseudocode below

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

Solution

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