109k views
1 vote
the java insertionsort() method's outer loop uses the variable i. what is true of list content with respect to i?

User Kikkpunk
by
8.2k points

1 Answer

4 votes

In the insertion sort algorithm, the outer loop iterates over the list using the index variable i. Here are some key facts about how the list content relates to i in the outer loop:

- The sub-list from 0 to i-1 is sorted after each iteration. The elements to the right of i are unsorted.

- i represents the delimiter between the sorted and unsorted parts of the list.

- On each iteration, the element at index i is 'inserted' into the correct position in the sorted sub-list from 0 to i-1.

- So as i increments, the sorted region grows by one element each time.

- When i reaches the end of the list, the entire list is sorted.

- The inner loop repeatedly swaps element i backwards until it is in sorted position within the sorted sub-list 0 to i-1.

So in summary, i represents the split between sorted and unsorted parts of the list, and increments by 1 each iteration to grow the sorted region from left to right. The inner loop positions element i correctly each time.

User Karlee
by
8.6k points