Engineering Questions with Answers - Multiple Choice Questions

# Insertion Sort Multiple Choice MCQ

1 - Question

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

View Answer

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

2 - Question

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 - Question

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(N2)

View Answer

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

4 - Question

Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
a) True
b) False

View Answer

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

5 - Question

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.

6 - Question

What is the running time of an insertion sort algorithm if the input is pre-sorted?
a) O(N2)
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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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.