AP Computer Science Exam Question:

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

public class InsertionSort {
    
    public static void sort(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, 3};
        sort(arr);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Explain how the Insertion Sort algorithm works and provide a step-by-step breakdown of the sorting process for the given input array [5, 2, 9, 1, 3]. Show the intermediate steps after each iteration of the outer loop.

Answer:

The Insertion Sort algorithm works by dividing the given array into two subarrays: a sorted subarray and an unsorted subarray. The algorithm iterates through the unsorted subarray and repeatedly selects an element, compares it with the elements in the sorted subarray, and inserts it into the correct position in the sorted subarray.

Now, let's step through the sorting process of the input array [5, 2, 9, 1, 3] using the Insertion Sort algorithm:

Iteration 1:

• Initial Array: [5, 2, 9, 1, 3]
• Select the first unsorted element, which is 2.
• Compare it with the elements in the sorted subarray [5].
• Since 2 is smaller than 5, shift 5 to the right.
• Intermediate Array: [2, 5, 9, 1, 3]
• Insert the selected element, 2, into its correct position in the sorted subarray.
• Intermediate Array: [2, 5, 9, 1, 3]

Iteration 2:

• Initial Array: [2, 5, 9, 1, 3]
• Select the second unsorted element, which is 9.
• Compare it with the elements in the sorted subarray [2, 5].
• Since 9 is greater than 5, no shifting is required.
• Intermediate Array: [2, 5, 9, 1, 3]
• Insert the selected element, 9, into its correct position in the sorted subarray.
• Intermediate Array: [2, 5, 9, 1, 3]

Iteration 3:

• Initial Array: [2, 5, 9, 1, 3]
• Select the third unsorted element, which is 1.
• Compare it with the elements in the sorted subarray [2, 5, 9].
• Since 1 is smaller than 9, shift 9 to the right and then shift 5 to the right.
• Intermediate Array: [2, 5, 5, 9, 3]
• Since 1 is also smaller than 5, shift 5 to the right.
• Intermediate Array: [2, 2, 5, 9, 3]
• Insert the selected element, 1, into its correct position in the sorted subarray.
• Intermediate Array: [1, 2, 5, 9, 3]

Iteration 4:

• Initial Array: [1, 2, 5, 9, 3]
• Select the fourth unsorted element, which is 3.
• Compare it with the elements in the sorted subarray [1, 2, 5, 9].
• Since 3 is smaller than 9, shift 9 to the right and then shift 5 to the right.
• Intermediate Array: [1, 2, 5, 5, 9]
• Since 3 is smaller than 5, shift 5 to the right and then shift 2 to the right.
• Intermediate Array: [1, 2, 2, 5, 9]
• Since 3 is also smaller than 2, shift 2 to the right.
• Intermediate Array: [1, 1, 2, 5, 9]
• Insert the selected element, 3, into its correct position in the sorted subarray.
• Intermediate Array: [1, 2, 3, 5, 9]

Final Sorted Array: [1, 2, 3, 5, 9]

At the end of the sorting process, the given input array [5, 2, 9, 1, 3] is sorted in ascending order, resulting in the array [1, 2, 3, 5, 9].