Insertion Sort Interview Questions and Answers

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Insertion Sort – 2”.

1. Which of the following is correct with regard to insertion sort?
a) insertion sort is stable and it sorts In-place
b) insertion sort is unstable and it sorts In-place
c) insertion sort is stable and it does not sort In-place
d) insertion sort is unstable and it does not sort In-place
View Answer

Answer: a
Explanation: During insertion sort, the relative order of elements is not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Therefore, it sorts In-place.

2. Which of the following sorting algorithm is best suited if the elements are already sorted?
a) Heap Sort
b) Quick Sort
c) Insertion Sort
d) Merge Sort
View Answer

Answer: c
Explanation: The best case running time of the insertion sort is O(n). The best case occurs when the input array is already sorted. As the elements are already sorted, only one comparison is made on each pass, so that the time required is O(n).

3. The worst case time complexity of insertion sort is O(n²). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?
a) O(nlogn)
b) O(n²)
c) O(n)
d) O(logn)
View Answer

Answer: b
Explanation: The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n²) because of the series of swapping operations required for each insertion.

4. Insertion sort is an example of an incremental algorithm.
a) True
b) False
View Answer

Answer: a
Explanation: In the incremental algorithms, the complicated structure on n items is built by first building it on n − 1 items. And then we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one element at a time. Therefore, it is an example of an incremental algorithm.

5. Consider the code given below, which runs insertion sort:

Note: Join free Sanfoundry classes at Telegram or Youtube

void insertionSort(int arr[], int array_size)
{
  int i, j, value;
  for (i = 1; i < array_size; i++)
  {
          value = arr[i];
          j = i;
          while (________ )
          {
                   arr[j] = arr[j − 1];
                   j = j − 1;
          }
          arr[j] = value;
  }
}

Which condition will correctly implement the while loop?
a) (j > 0) || (arr[j − 1] > value)
b) (j > 0) && (arr[j − 1] > value)
c) (j > 0) && (arr[j + 1] > value)
d) (j > 0) && (arr[j + 1] < value)
View Answer

Answer: b
Explanation: In insertion sort, the element is A[j] is inserted into the correct position in the sorted sequence A[1… j – 1]. So, condition given in (j > 0) && (arr[j − 1] > value) will implement while loop correctly.

6. Which of the following is good for sorting arrays having less than 100 elements?
a) Quick Sort
b) Selection Sort
c) Merge Sort
d) Insertion Sort
View Answer

Answer: d
Explanation: The insertion sort is good for sorting small arrays. It sorts smaller arrays faster than any other sorting algorithm.

7. Consider an array of length 5, arr[5] = {9,7,4,2,1}. What are the steps of insertions done while running insertion sort on the array?
a) 7 9 4 2 1    4 7 9 2 1    2 4 7 9 1    1 2 4 7 9
b) 9 7 4 1 2    9 7 1 2 4    9 1 2 4 7    1 2 4 7 9
c) 7 4 2 1 9    4 2 1 9 7    2 1 9 7 4    1 9 7 4 2
d) 7 9 4 2 1    2 4 7 9 1    4 7 9 2 1    1 2 4 7 9
View Answer

Answer: a
Explanation: The steps performed while running insertion sort on given array are:
Initial : 9 7 4 2 1 key = 7
             7 9 4 2 1 key = 4
             4 7 9 2 1 key = 2
             2 4 7 9 1 key = 1
             1 2 4 7 9

In each step, the key is the element that is compared with the elements present at the left side to it.

8. Statement 1: In insertion sort, after m passes through the array, the first m elements are in sorted order.
Statement 2: And these elements are the m smallest elements in the array.
a) Both the statements are true
b) Statement 1 is true but statement 2 is false
c) Statement 1 is false but statement 2 is true
d) Both the statements are false
View Answer

Answer: b
Explanation: In insertion sort, after m passes through the array, the first m elements are in sorted order but they are whatever the first m elements were in the unsorted array.

9. In insertion sort, the average number of comparisons required to place the 7^th element into its correct position is ____
a) 9
b) 4
c) 7
d) 14
View Answer

Answer: b
Explanation: On average (k + 1) / 2 comparisons are required to place the k^th element into its correct position. Therefore, average number of comparisons required for 7th element = (7 + 1)/2 = 4.

10. Which of the following is not an exchange sort?
a) Bubble Sort
b) Quick Sort
c) Partition-exchange Sort
d) Insertion Sort
View Answer

Answer: d
Explanation: In Exchange sorts, we compare each element of an array and swap those elements that are not in their proper position. Bubble Sort and Quick Sort are exchange sorts. Quick Sort is also called as Partition-exchange Sort. Insertion sort is not an exchange sort.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Insertion Sort Multiple Choice Questions and Answers

» Next - Data Structure Questions and Answers – Selection Sort

Related Posts:

Recommended Articles: