Which of the following best describes the state of the array just before the fin

Question

Which of the following best describes the state of the array just before the final iteration of the outermost loop in Insertion Sort? (Don't pick an answer that is only true in special cases.)

A : The first N-1 elements of the array are sorted relative to each other, leaving only the final element potentially out of order.

B : The array is sorted besides two out-of-order elements, which should be swapped.

C : The array is actually sorted already, and just needs a final pass to check that this is the case.

D : The item that used to be at the end of the array is now one space away from where it should be.

Explanation / Answer

Both statement A & D best describes Insertion sort.

The loop invariant for the outer loop is like before, that after nth iteration, all elements till current n will be sorted.
Just before the nth interation, all values (or) elements till n-1 will be sorted.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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