Data Structures & Algorithms Multiple Choice Questions on “Insertion Sort”.
1. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N2
Answer: b
Clarification: 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
Answer: a
Clarification: 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(N2)
Answer: d
Clarification: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N2).
4. Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
a) True
b) False
View Answer
Answer: a
Clarification: Each swap removes only one inversion, so O(N2) 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
Answer: a
Clarification: 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. 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)
Answer: c
Clarification: 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
Answer: b
Clarification: 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
Answer: d
Clarification: 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
Clarification: 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: The worst case input for an insertion sort algorithm will be an array sorted in reverse order and its running time is quadratic.