Insertion Sort Interview Question Part 1

1.Insertion sort is 1.in-place 2.out-place 3.stable 4.non-stable
a.1 and 3 b.1 and 4 c.2 and 3 d.2 and 4
Ans:a
The array is sorted in-place because no extra memory is required. Stable sort retains the original ordering of keys when identical keys are present in the input data.


2.Sorting of playing cards is an example of
a.Bubble sort b. Insertion sort c.Selection sort d.Quick sort
Ans:b

3. For insertion sort, the number of entries we must index through when there are n elements in the array is
a. n entries b.n*n entries c.n-1 entries d.none of the above
Ans:c
Assuming there are n elements in the array we must index through n - 1 entries. For each entry we may need to examine and shift up to n - 1 other entries resulting in a O(n2) algorithm.

4.What is the average case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

5.What is the worst case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b


6. What is the best case complexity for insertion sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:a

7.What is the output of insertion sort after the 1st iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:a

8. The following loop is used for
For i<- 1 to N-1
{
For j<- i+1 to N
{
If(a(j) {
Temp=a(j);
For k<- j to i+1
A[k]=a[k-1];
}
}
A(i)=temp;
}
a.bubble sort b.selection sort c.insertion sort d.merge sort
Ans:c


9. Total number of comparisons for insertion sort is
a.n(n-1)/2
b. n(n+1)/2
c.n
d.n*n
Ans:a

10. In which cases are the time complexities same in insertion sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:c

11. What is the output of insertion sort after the 2nd iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 5 7 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:a

12.What is the output of insertion sort after the 3rd iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 5 7 9 8 4 6
Ans:d