Given: 1. void insertionSort (int values[]) { 2. int n = values.length; 3. for (int i = 1; i = 0 && (values[j] > tmp)) { 7. values[j + 1] = values[j]; 8. j--; 9. } 10. values[j + 1] = tmp; 11. } 12. } After which line can we insert insert i < 0 || values[i] <= values[i + 1]; to verify that the values array is partially sorted?

Oracle

1Z0-819 · Question #85

Given: 1. void insertionSort (int values[]) { 2. int n = values.length; 3. for (int i = 1; i < n; i++) { 4. int tmp = values[i]; 5. int j = i - 1; 6. while (j >= 0 && (values[j] > tmp)) { 7…

The correct answer is B. After line 6. After line 6 is correct because that is when the inner while loop exits, meaning the algorithm has just determined the correct insertion position - either j went below 0 (all remaining left-side elements are greater than tmp) or values[j] <= tmp. At that exit point, the partial…

Working with Arrays and Collections

Question

Given:
void insertionSort (int values[]) {
int n = values.length;
for (int i = 1; i < n; i++) {
int tmp = values[i];
int j = i - 1;
while (j >= 0 && (values[j] > tmp)) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = tmp;
}
}
After which line can we insert insert i < 0 || values[i] <= values[i + 1]; to verify that the values array is partially sorted?

Options

AAfter line 8
BAfter line 6
CAfter line 5
DAfter line 10

How the community answered

(15 responses)

A
13% (2)
B
80% (12)
C
7% (1)

Explanation

After line 6 is correct because that is when the inner while loop exits, meaning the algorithm has just determined the correct insertion position - either j went below 0 (all remaining left-side elements are greater than tmp) or values[j] <= tmp. At that exit point, the partial sortedness invariant i < 0 || values[i] <= values[i + 1] is validly checkable: the shifted elements above the insertion point are all greater than tmp, and everything below is in sorted order relative to tmp.

After line 5 (C) is wrong because j has just been initialized and no comparisons or shifts have occurred yet - there is nothing to assert about sortedness.

After line 8 (A) is wrong because j has just decremented and values are mid-shift in a transitional, inconsistent state; the invariant cannot be verified while the loop body is still executing.

After line 10 (D) is wrong because although values[0..i] is now fully sorted, values[i+1] is still an unprocessed element - there is no guarantee that values[i] <= values[i+1], so the assertion would fail spuriously.

Memory tip: Think of the while loop exit as the "checkpoint" - only when the inner loop stops does the algorithm know where insertion belongs, so that's the one moment you can safely assert partial order.

Topics

#insertion sort#partial sorting invariant#algorithm analysis#assertion placement

Community Discussion

No community discussion yet for this question.

Full 1Z0-819 Practice