1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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
Explanation: An insertion sort is stable, adaptive, in-place and incremental in nature.
8. 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.
9. 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
Explanation: The best case input for an insertion sort algorithm runs in linear time and is given by O(N).
10. 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
Explanation: The worst case input for an insertion sort algorithm will be an array sorted in reverse order and its running time is quadratic.
Design and Analysis of Algorithms
The Basics: Sorting Made Simple
Imagine you're a librarian with a stack of books in a chaotic order. Now, your goal is to arrange them neatly on the shelves. What do you do? You pick up a book, compare it with the ones already on the shelf, and find its perfect spot – that's Insertion Sort in a nutshell!
Step by Step Elegance
1. Picking Partners: Insertion Sort takes each element and places it where it belongs, one at a time. No VIP treatment here, every element gets its moment in the spotlight.
2. Jigsaw Puzzle: It's like solving a jigsaw puzzle. You start with one piece, fitting it snugly, and then proceed with the next until the picture is complete.
3. Back to Basics: This algorithm is your algorithmic grandma, reminding you of the good old days when life was simpler. It's not fancy, but boy, does it get the job done!
Why Insertion Sort?
Efficiency in Small Doses: While it might not be your go-to for massive datasets, Insertion Sort shines when dealing with smaller arrays.
Adaptive Nature: Insertion Sort is like a chameleon – it adapts. If elements are nearly sorted, it becomes an algorithmic ninja, swift and efficient.
Memory Saver: If you're tight on memory, Insertion Sort is your friend. It's lightweight and won’t hog your system resources.
So, there you have it – Insertion Sort, the unsung hero of sorting algorithms, and a sneak peek into conquering Design and Analysis of Algorithms MCQs. Now, go forth, sort those algorithms, and ace those quizzes! Happy coding!