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

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

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)

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

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

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)

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

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

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

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

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

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?
b) dependable
c) stable, not in-place

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

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
d) Depends on the input

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