Question

The Insertion sort has two loops. The outer loop moves element by element through the array whereas the inner loop compares the element chosen in the outer loop to the element next to it in the array. If the element selected by the outer loop is less than the element selected by the inner loop, array elements are shifted over to the right to make room for the inner loop element. What is the purpose of the inner loop in Insertion sort?

1) To compare the element chosen in the outer loop to the element next to it in the array
2) To move elements over to the right to make room for the inner loop element
3) To select the element with the smallest value in the array
4) To sort the array in ascending order

Answer 1

The inner loop in Insertion sort moves elements to the right to make room for the current element being sorted, ensuring elements are inserted in their correct positions in an ascending order.

Step-by-step explanation:

The inner loop in Insertion sort has the primary purpose of comparing the temporarily removed element, chosen by the outer loop, with the elements in the sorted portion of the array to find the correct position for this element. When an element in the inner loop is found to be greater than the element selected by the outer loop, the inner loop moves these larger elements one position to the right, thereby making room for the newly selected element to be inserted. Hence, the inner loop is responsible both for creating the right space in the sorted portion of the array and for ensuring continued sorting until the array is completely sorted in ascending order.

The correct answer to the question of what the purpose of the inner loop in Insertion sort is option 2) To move elements over to the right to make room for the inner loop element. The inner loop's role encompasses the shifting process which is critical for maintaining the sorted array structure while allowing new elements to be inserted in their proper place.