Test on Insertion sort

Question 1: During the insertion sort process, if an element in the sorted sub-array is greater than the key, it is shifted one position to the right to make space for the key.

A. Yes

B. No

Explanation: When the key is being inserted into the sorted sub-array, the algorithm compares the key with elements already in the sorted part. If an element in the sorted sub-array is found to be greater than the key, it is shifted one position to the right. This action creates the necessary space for the key to be inserted into its correct sorted position.

Question 2: According to the provided study materials, which statement accurately describes how the 'key' is selected during the iteration phase of the Insertion Sort algorithm?

A. The first element of the array is always chosen as the key.

B. The 'key' is the current element taken from the unsorted part of the array.

C. The smallest element remaining in the unsorted part is designated as the 'key'.

D. The last element of the sorted sub-array becomes the 'key'.

Explanation: The study materials state under 'How Insertion Sort Works: Step-by-Step', point 2.a: 'Select Key: Take the current element from the unsorted part. This element is often referred to as the 'key'.' This directly matches the selection of the current element from the unsorted part.

Question 3: For an already sorted array in ascending order, Insertion Sort in its best-case scenario requires frequent shifting of elements.

A. Yes

B. No

Explanation: The study materials state that in the best-case scenario, which occurs when the array is already sorted, 'No elements need to be shifted.' This contradicts the idea that frequent shifting is required.

Question 4: Insertion Sort exhibits a worst-case time complexity of O(n²) when the array is sorted in reverse order.

A. Yes

B. No

Explanation: The study materials state that the worst-case time complexity for Insertion Sort is O(n²), and this occurs when the array is sorted in reverse order. For example, with an array like [5, 4, 3, 2, 1], each element must be compared with all elements in the sorted sub-array and shifted, leading to approximately n²/2 operations, which is proportional to n².

Question 5: According to the provided materials, which statement accurately describes why Insertion Sort is considered adaptive?

A. Its performance improves for data sets that are already partially sorted, approaching linear time complexity for nearly sorted arrays.

B. It is adaptive because it sorts the array in-place, modifying the original array directly.

C. It is adaptive because it maintains the relative order of elements with equal values.

D. Its performance significantly degrades for nearly sorted arrays, reaching quadratic time complexity.

Explanation: The study materials state that Insertion sort is adaptive, which means its performance improves for data sets that are already partially sorted. It performs exceptionally well for nearly sorted arrays, approaching linear time complexity (O(n)). The best-case scenario, where the array is already sorted, results in O(n) time complexity, further supporting its adaptive nature. Option 1 directly reflects this property. Options 2 and 3 describe 'in-place' and 'stable' properties, respectively, not adaptive. Option 4 is incorrect as its performance improves, not degrades, for nearly sorted arrays.