Consider the following correct implementation of the insertion sort algorithm. The insertionSort method correctly sorts the elements of ArrayList data into increasing order.
public static void insertionSort(ArrayList data)
{
for (int j = 1; j < data.size(); j++)
{
int v = data.get(j);
int k = j;
while (k > 0 && v < data.get(k - 1))
{
data.set(k, data.get(k - 1)); / Statement 1 /
k--;
}
data.set(k, v); / Statement 2 /
/ End of outer loop /
}
}
Assume that insertionSort has been called with an ArrayList parameter that has been initialized with the following Integer objects.
[5, 2, 4, 1, 3, 6]
What will the contents of data be after three passes of the outside loop (i.e., when j == 3 at the point indicated by / End of outer loop /) ?