Question:

Consider the following code snippet that implements the Insertion Sort algorithm:

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};
        insertionSort(arr);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Explain what happens at each iteration of the outer loop in the insertionSort method and provide the output produced by the code.

Answer:

During each iteration of the outer loop in the insertionSort method, an element is selected from the unsorted part of the array and inserted into its correct position within the sorted part of the array.

1. Iteration 1:

   • key = 2
   • j = 0
   • arr[0] = 5
   • 5 is greater than 2, so arr[1] = 5
   • j = -1
   • arr[0] = 2
   • Array after iteration 1: [2, 5, 9, 1, 7]

2. Iteration 2:

   • key = 9
   • j = 1
   • arr[1] = 5
   • 5 is less than 9, so the loop terminates
   • arr[2] = 9
   • Array after iteration 2: [2, 5, 9, 1, 7]

3. Iteration 3:

   • key = 1
   • j = 2
   • arr[2] = 9
   • 9 is greater than 1, so arr[3] = 9
   • j = 1
   • arr[2] = 5
   • 5 is greater than 1, so arr[2] = 5
   • j = 0
   • arr[1] = 2
   • 2 is greater than 1, so arr[1] = 2
   • j = -1
   • arr[0] = 1
   • Array after iteration 3: [1, 2, 5, 9, 7]

4. Iteration 4:

   • key = 7
   • j = 3
   • arr[3] = 9
   • 9 is greater than 7, so arr[4] = 9
   • j = 2
   • arr[3] = 5
   • 5 is less than 7, so the loop terminates
   • arr[3] = 7
   • Array after iteration 4: [1, 2, 5, 7, 9]

The output produced by the code is: 1 2 5 7 9

Note: The sorted part of the array is shown in brackets for better clarity.