Engineering Questions with Answers - Multiple Choice Questions

# Insertion Sort Multiple Choice MCQ – 2

1 - Question

Which of the following is correct with regard to insertion sort?
a) insertion sort is stable and it sorts In-place
b) insertion sort is unstable and it sorts In-place
c) insertion sort is stable and it does not sort In-place
d) insertion sort is unstable and it does not sort In-place

Explanation: During insertion sort, the relative order of elements is not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Therefore, it sorts In-place.

2 - Question

Which of the following sorting algorithm is best suited if the elements are already sorted?
a) Heap Sort
b) Quick Sort
c) Insertion Sort
d) Merge Sort

Explanation: The best case running time of the insertion sort is O(n). The best case occurs when the input array is already sorted. As the elements are already sorted, only one comparison is made on each pass, so that the time required is O(n).

3 - Question

The worst case time complexity of insertion sort is O(n2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?
a) O(nlogn)
b) O(n2)
c) O(n)
d) O(logn)

Explanation: The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n2) because of the series of swapping operations required for each insertion.

4 - Question

Insertion sort is an example of an incremental algorithm.
a) True
b) False

Explanation: In the incremental algorithms, the complicated structure on n items is built by first building it on n − 1 items. And then we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one element at a time. Therefore, it is an example of an incremental algorithm.

5 - Question

Consider the code given below, which runs insertion sort:

```void insertionSort(int arr[], int array_size)
{
int i, j, value;
for (i = 1; i < array_size; i++)
{
value = arr[i];
j = i;
while (________ )
{
arr[j] = arr[j − 1];
j = j − 1;
}
arr[j] = value;
}
}```

Which condition will correctly implement the while loop?
a) (j > 0) || (arr[j − 1] > value)
b) (j > 0) && (arr[j − 1] > value)
c) (j > 0) && (arr[j + 1] > value)
d) (j > 0) && (arr[j + 1] < value)

Explanation: In insertion sort, the element is A[j] is inserted into the correct position in the sorted sequence A[1… j – 1]. So, condition given in (j > 0) && (arr[j − 1] > value) will implement while loop correctly.

6 - Question

Which of the following is good for sorting arrays having less than 100 elements?
a) Quick Sort
b) Selection Sort
c) Merge Sort
d) Insertion Sort

Explanation: The insertion sort is good for sorting small arrays. It sorts smaller arrays faster than any other sorting algorithm.

7 - Question

Consider an array of length 5, arr = {9,7,4,2,1}. What are the steps of insertions done while running insertion sort on the array?
a) 7 9 4 2 1 4 7 9 2 1 2 4 7 9 1 1 2 4 7 9
b) 9 7 4 1 2 9 7 1 2 4 9 1 2 4 7 1 2 4 7 9
c) 7 4 2 1 9 4 2 1 9 7 2 1 9 7 4 1 9 7 4 2
d) 7 9 4 2 1 2 4 7 9 1 4 7 9 2 1 1 2 4 7 9

Explanation: The steps performed while running insertion sort on given array are:
Initial : 9 7 4 2 1 key = 7
7 9 4 2 1 key = 4
4 7 9 2 1 key = 2
2 4 7 9 1 key = 1
1 2 4 7 9
In each step, the key is the element that is compared with the elements present at the left side to it.

8 - Question

Statement 1: In insertion sort, after m passes through the array, the first m elements are in sorted order.
Statement 2: And these elements are the m smallest elements in the array.
a) Both the statements are true
b) Statement 1 is true but statement 2 is false
c) Statement 1 is false but statement 2 is true
d) Both the statements are false

Explanation: In insertion sort, after m passes through the array, the first m elements are in sorted order but they are whatever the first m elements were in the unsorted array.

9 - Question

In insertion sort, the average number of comparisons required to place the 7th element into its correct position is ____
a) 9
b) 4
c) 7
d) 14

Explanation: On average (k + 1) / 2 comparisons are required to place the kth element into its correct position. Therefore, average number of comparisons required for 7th element = (7 + 1)/2 = 4.

10 - Question

Which of the following is not an exchange sort?
a) Bubble Sort
b) Quick Sort
c) Partition-exchange Sort
d) Insertion Sort