Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Aeronautical Engineering » Insertion Sort Multiple Choice MCQ

# Insertion Sort Multiple Choice MCQ

How many passes does an insertion sort algorithm consist of?

a) N

b) N-1

c) N+1

d) N^{2}

**
View Answer**

Answer: b

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

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.

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^{2})

**
View Answer**

Answer: d

Explanation: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N^{2}).

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(N^{2}) swaps are required.

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.

What is the running time of an insertion sort algorithm if the input is pre-sorted?

a) O(N^{2})

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.

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.

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.

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.

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.

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.

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.

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.

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).

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.