AP Computer Science Exam Question:

Consider the following implementation of the Insertion Sort algorithm in Java:

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; 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;
    }
}

a) Explain the purpose of the insertionSort method.

b) Demonstrate the step-by-step execution of the insertionSort method on the following array:

int[] arr = {5, 2, 8, 3, 1};

Provide the intermediate state of the array after each iteration of the outer loop.

c) What is the time complexity of the Insertion Sort algorithm? Justify your answer.

Answer:

a) The insertionSort method implements the Insertion Sort algorithm, which is a comparison-based sorting algorithm. It repeatedly finds the appropriate position (or slot) for each element in the array, and inserts it there, while maintaining the sorted portion of the array.

b) Step-by-step execution of the insertionSort method on the array int[] arr = {5, 2, 8, 3, 1}:

1. Initial state: [5, 2, 8, 3, 1]

   After first iteration of the outer loop (i = 1):

   • key = 2
   • Move elements greater than key one position ahead: [5, 5, 8, 3, 1]
   • Insert key at the appropriate position: [2, 5, 8, 3, 1]

   Intermediate state: [2, 5, 8, 3, 1]

2. Intermediate state: [2, 5, 8, 3, 1]

   After second iteration of the outer loop (i = 2):

   • key = 8
   • Element 2 is in its correct position in the sorted portion
   • Insert key at the appropriate position: [2, 5, 8, 3, 1]

   Intermediate state: [2, 5, 8, 3, 1]

3. Intermediate state: [2, 5, 8, 3, 1]

   After third iteration of the outer loop (i = 3):

   • key = 3
   • Move elements greater than key one position ahead: [2, 5, 8, 8, 1]
   • Move elements greater than key one position ahead: [2, 5, 5, 8, 1]
   • Insert key at the appropriate position: [2, 3, 5, 8, 1]

   Intermediate state: [2, 3, 5, 8, 1]

4. Intermediate state: [2, 3, 5, 8, 1]

   After fourth iteration of the outer loop (i = 4):

   • key = 1
   • Move elements greater than key one position ahead: [2, 3, 5, 8, 8]
   • Move elements greater than key one position ahead: [2, 3, 5, 5, 8]
   • Move elements greater than key one position ahead: [2, 3, 3, 5, 8]
   • Move elements greater than key one position ahead: [2, 2, 3, 5, 8]
   • Insert key at the appropriate position: [1, 2, 3, 5, 8]

   Intermediate state: [1, 2, 3, 5, 8]

Final sorted array: [1, 2, 3, 5, 8]

c) The time complexity of the Insertion Sort algorithm is O(n^2), where n is the number of elements in the array.

This can be justified by observing that the inner while loop may iterate up to i times, where i is the current index of the outer loop. In the worst case, when the array is sorted in descending order, each inner loop iteration would move all elements before the current index by one position, resulting in a quadratic time complexity. However, in the best case scenario, when the array is already sorted, the inner loop would terminate immediately in each iteration, resulting in a linear time complexity.