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

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

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

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

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

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

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

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

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

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

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;
}

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

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

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

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; 
    } 
}

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]