Insertion Sort – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

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

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: The running time is O(N) if the input is pre-sorted, since the inner for loop’s test 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: N-1 denotes the number of passes. N=6 in this case. As a result, 6-1=5 is right.

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: The array would look like this after the second pass of swapping elements: 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: An insertion sort is imitated by arranging a pack of cards. A merge sort scenario is a database, arranging books is a stack, and real-time systems use fast 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: We use two simple loops to perform an insertion sort: 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: In an insertion sort algorithm, binary search can be used to reduce the number of comparisons. A Binary insertion type is what it’s called.

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: The essence of an insertion sort is that it is secure, adaptive, in-place, and gradual.

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: Insertion sort is faster than simple sort for sorting small arrays. However, sorting massive arrays is impractical.

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 is O, which runs in linear time (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: An array sorted in reverse order is the worst case input for an insertion sort algorithm, and its running time is quadratic.

11. How many passes does an insertion sort algorithm consist of?
A) N
B) N-1
C) N+1
D) N2

Explanation: When given an array of N elements, an insertion algorithm consists of N-1 passes.

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

Explanation: Because of the use of temporary variables to swap, insertion sort is similar to a binary heap algorithm.

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

Explanation: A tight bound algorithm’s average case analysis is mathematically determined to be O. (N2).

14. Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
A) True
B) False

Explanation: Since each swap only removes one inversion, O(N2) swaps are required.

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

Explanation: In a list L, the total number of pairs is N(N-1)/2. As a result, a typical list has half as many inversions, or N(N-1)/4 inversions.

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

Explanation: For sorting small arrays, the insertion sort is useful. It is better than any other sorting algorithm at sorting smaller arrays.

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

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.

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

Explanation: After m passes through the array, the first m elements are in sorted order, but they are whatever the unsorted array’s first m elements were.

19. In insertion sort, the average number of comparisons required to place the 7th element into its correct position is ____
A) 9
B) 4
C) 7
D) 14

Explanation: To place the kth element in its proper location, on average (k + 1) / 2 comparisons are needed. As a result, the average number of comparisons required for the seventh factor is (7 + 1)/2 = 4.

20. Which of the following is not an exchange sort?
A) Bubble Sort
B) Quick Sort
C) Partition-exchange Sort
D) Insertion Sort

Explanation: We compare each member of an array and swap those that are not in their proper place in Exchange sorts. Exchange kinds are Bubble Sort and Fast Sort. Partition-exchange Sort is another name for Fast Sort. The insertion sort is not the same as the exchange sort.

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

Explanation: The relative order of elements is not modified during insertion sort. As a result, it’s a reliable sorting algorithm. In addition, insertion sort only takes up O(1) additional memory space. As a result, it sorts in place.

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

Explanation: The insertion sort’s best case running time is O. (n). When the input list is already sorted, the best case scenario occurs. Since the elements have already been sorted, each pass only requires one contrast, resulting in an O time requirement (n).

23. The worst case time complexity of insertion sort is O(n2). 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(n2)
C) O(n)
D) O(logn)

Explanation: Binary search reduces the time it takes to find the right location from O(n) to O(n) (logn). However, since each insertion requires a set of swapping operations, the worst case of insertion sort remains O(n2).

24. Insertion sort is an example of an incremental algorithm.
A) True
B) False

Explanation: The complicated structure on n items is constructed using incremental algorithms by first constructing it on n 1 items. Then, in order to add the final object, we make the required changes. The sorted sequence is built one element at a time using insertion sort. As a result, it is an example of a progressive algorithm.

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

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)

Explanation: The element A[j] is inserted into the correct place in the sorted sequence A[1… j – 1] in insertion sort. As a result, the condition (j > 0) && (arr[j 1] > value) will correctly enforce the while loop.

Insertion sort is a simple sorting algorithm in which each object in the final sorted array (or list) is added one at a time. On wide lists, it is much less effective than more sophisticated algorithms like quicksort, heapsort, or merge sort. A sorted array is a data structure in which each element is sorted in numerical, alphabetical, or other order and stored in computer memory at evenly spaced addresses. It’s most commonly used in computer science to create static lookup tables that store multiple values of the same data type. Sorting an array is useful for putting data in order and retrieving it quickly.

Leave a Reply

Your email address will not be published. Required fields are marked *