Data Structures & Algorithms Multiple Choice Questions on “Insertion Sort”.
1. 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
Answer: a
Clarification: 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. 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
Answer: c
Clarification: 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. 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)
Answer: b
Clarification: 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. Insertion sort is an example of an incremental algorithm.
a) True
b) False
Answer: a
Clarification: 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. 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)
Answer: b
Clarification: 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. 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
View Answer
Answer: d
Clarification: The insertion sort is good for sorting small arrays. It sorts smaller arrays faster than any other sorting algorithm.
7. Consider an array of length 5, arr[5] = {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
View Answer
Answer: a
Clarification: 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. 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
Answer: b
Clarification: 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. 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
Answer: b
Clarification: 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. Which of the following is not an exchange sort?
a) Bubble Sort
b) Quick Sort
c) Partition-exchange Sort
d) Insertion Sort
Answer: d
Clarification: In Exchange sorts, we compare each element of an array and swap those elements that are not in their proper position. Bubble Sort and Quick Sort are exchange sorts. Quick Sort is also called as Partition-exchange Sort. Insertion sort is not an exchange sort.