Binary Insertion Sort Multiple Choice Questions and Answers (MCQs)

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

1. Which of the following is an advantage of binary insertion sort over its standard version?
a) it has better time complexity
b) it has better space complexity
c) it makes less number of comparisons
d) it has no significant advantage
View Answer

Answer: c
Explanation: Binary insertion sort makes less number of comparisons as compared to the standard version of insertion sort. Binary insertion sort makes log n comparisons in the worst case as compared to n comparisons made in the standard version.

2. Binary Insertion sort is an online sorting algorithm.
a) True
b) False
View Answer

Answer: a
Explanation: Binary Insertion sort does not require the entire input data at the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.

3. How many comparisons will be made in the worst case when an array of size n will be sorted by using a binary insertion sort algorithm?
a) n
b) 1
c) log n
d) n log n
View Answer

Answer: c
Explanation: Binary insertion sort makes log n comparisons in the worst case. Whereas the standard version makes n comparisons in the worst case.
advertisement
advertisement

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Binary insertion sort
d) Heap sort
View Answer

Answer: c
Explanation: Out of the given options binary insertion sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

5. Which of the following sorting algorithm uses a binary search?
a) radix sort
b) binary insertion sort
c) odd-even sort
d) bead sort
View Answer

Answer: b
Explanation: Binary insertion sort makes use of a binary search algorithm. It is used to find the correct index in the array where the element should be inserted.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Binary insertion sort is a comparison based sort.
a) true
b) false
View Answer

Answer: a
Explanation: In insertion sort, we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of binary insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Explanation: The time complexity does not change when we use binary insertion sort in place of standard insertion sort. So the average case time complexity is O(n2).
advertisement

8. What is the best case time complexity of binary insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: a
Explanation: The best case time complexity of binary insertion sort is O(n). It occurs in the case when the input is already/almost sorted.

9. What is the worst case time complexity of binary insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Explanation: The time complexity does not change when we use binary insertion sort in place of standard insertion sort. So the worst case time complexity is O(n2).
advertisement

10. Choose the correct statement regarding binary insertion sort?
a) It has a better time complexity as compared to the standard version
b) It has a better space complexity as compared to the standard version
c) it takes less number of comparisons in the best case as compared to the standard version
d) it takes less number of comparisons in the worst case as compared to the standard version
View Answer

Answer: d
Explanation: Binary insertion sort has the advantage that it takes less number of comparisons in the worst case as compared to the standard version. In the best case, both standard insertion sort and binary insertion sort makes only 1 comparison.

11. What will be the base case in the function of binary search used in the code of binary insertion sort? (high and low are the rightmost and leftmost index of array respectively and item is the element whose correct position is to be determined by the binary search function)
a)

If(high<=low) 
{ 
    If(Item>a[low])
    return low+1;
    return low;
}

b)

If(high>=low)
{
    If(Item<a[low])
    return low+1;
    return low;
}

c)

If(high<=low)
{
    If(Item<a[low])
    return low;
    return low+1;
}

d)

If(high<=low)
{  
    If(Item>a[low])
    return low;
    return low+1;
}
View Answer
Answer: c
Explanation: The base case of binary search has to be made such that even when the element is not found in the array the function still returns the required index back to the function of insertion sort.
 
 

12. What is the auxiliary space complexity of binary insertion sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)
View Answer

Answer: b
Explanation: The auxiliary space required by a binary insertion sort is O(1). So it qualifies as an in place sorting algorithm.

13. Which of the following is an adaptive sorting algorithm?
a) binary insertion sort
b) merge sort
c) heap sort
d) selection sort
View Answer

Answer: a
Explanation: Binary insertion sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.

14. Which of the following sorting algorithm is in place?
a) binary insertion sort
b) merge sort
c) radix sort
d) counting sort
View Answer

Answer: a
Explanation: Out of the given options binary insertion sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).

15. Choose the correct function for binary insertion sort?
a)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
       //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j);  
       //where the key should be inserted        
        while (j >= index) 
        { 
            a[j+1] = a[j]; 
            j--; 
        } 
        a[j+1] = key; 
    } 
}

b)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i < =n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, j,0);  
        //where the key should be inserted
        while (j >= index) 
        { 
            a[j+1] = a[j]; 
            J++; 
        } 
        a[j+1] = key; 
    } 
}

c)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key;   
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j);  
        //where the key should be inserted        
        while (j <= index) 
        { 
            a[j+1] = a[j]; 
            j--; 
        } 
        a[j+1] = key; 
    } 
}

d)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j); 
        //where the key should be inserted        
        while (j <= index) 
        { 
            a[j+1] = a[j]; 
            J++; 
        } 
        a[j+1] = key; 
    } 
}
View Answer
Answer: a
Explanation: The code of binary insertion sort is same as the standard insertion sort except that we are finding the index where the key has to be inserted by using binary search. This reduces the number of comparisons.
 
 

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.