Insertion Sort MCQ - Sanfoundry

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Insertion Sort”.

1. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N²
View Answer

Answer: b
Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given.

2. Which of the following algorithm implementations is similar to that of an insertion sort?
a) Binary heap
b) Quick sort
c) Merge sort
d) Radix sort
View Answer

Answer: a
Explanation: Insertion sort is similar to that of a binary heap algorithm because of the use of temporary variable to swap.

3. What is the average case running time of an insertion sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)
View Answer

Answer: d
Explanation: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N²).

4. Any algorithm that sorts by exchanging adjacent elements require O(N²) on average.
a) True
b) False
View Answer

Answer: a
Explanation: Each swap removes only one inversion, so O(N²) swaps are required.

5. What is the average number of inversions in an array of N distinct numbers?
a) N(N-1)/4
b) N(N+1)/2
c) N(N-1)/2
d) N(N-1)/3
View Answer

Answer: a
Explanation: The total number of pairs in a list L is N(N-1)/2. Thus, an average list has half this amount, or N(N-1)/4 inversions.

Note: Join free Sanfoundry classes at Telegram or Youtube

6. What is the running time of an insertion sort algorithm if the input is pre-sorted?
a) O(N²)
b) O(N log N)
c) O(N)
d) O(M log N)
View Answer

Answer: c
Explanation: If the input is pre-sorted, the running time is O(N), because the test in the inner for loop always fails immediately and the algorithm will run quickly.

7. What will be the number of passes to sort the elements using insertion sort?
14, 12,16, 6, 3, 10
a) 6
b) 5
c) 7
d) 1
View Answer

Answer: b
Explanation: The number of passes is given by N-1. Here, N=6. Therefore,
6-1=5 passes.

8. For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21
a) 8, 21, 32, 34, 51, 64
b) 8, 32, 34, 51, 64, 21
c) 8, 34, 51, 64, 32, 21
d) 8, 34, 64, 51, 32, 21
View Answer

Answer: d
Explanation: After swapping elements in the second pass, the array will look like, 8, 34, 64, 51, 32, 21.

9. Which of the following real time examples is based on insertion sort?
a) arranging a pack of playing cards
b) database scenarios and distributes scenarios
c) arranging books on a library shelf
d) real-time systems
View Answer

Answer: a
Explanation: Arranging a pack of cards mimics an insertion sort. Database scenario is an example for merge sort, arranging books is a stack and real-time systems uses quick sort.

10. In C, what are the basic loops required to perform an insertion sort?
a) do- while
b) if else
c) for and while
d) for and if
View Answer

Answer: c
Explanation: To perform an insertion sort, we use two basic loops- an outer for loop and an inner while loop.

11. Binary search can be used in an insertion sort algorithm to reduce the number of comparisons.
a) True
b) False
View Answer

Answer: a
Explanation: Binary search can be used in an insertion sort algorithm to reduce the number of comparisons. This is called a Binary insertion sort.

12. Which of the following options contain the correct feature of an insertion sort algorithm?
a) anti-adaptive
b) dependable
c) stable, not in-place
d) stable, adaptive
View Answer

Answer: d
Explanation: An insertion sort is stable, adaptive, in-place and incremental in nature.

13. Which of the following sorting algorithms is the fastest for sorting small arrays?
a) Quick sort
b) Insertion sort
c) Shell sort
d) Heap sort
View Answer

Answer: b
Explanation: For sorting small arrays, insertion sort runs even faster than quick sort. But, it is impractical to sort large arrays.

14. For the best case input, the running time of an insertion sort algorithm is?
a) Linear
b) Binary
c) Quadratic
d) Depends on the input
View Answer

Answer: a
Explanation: The best case input for an insertion sort algorithm runs in linear time and is given by O(N).

15. Which of the following examples represent the worst case input for an insertion sort?
a) array in sorted order
b) array sorted in reverse order
c) normal unsorted array
d) large array
View Answer

Answer: b
Explanation: The worst case input for an insertion sort algorithm will be an array sorted in reverse order and its running time is quadratic.

More MCQs on Insertion Sort: