250+ TOP MCQs on Bead Sort and Answers

Data Structures & Algorithms Multiple Choice Questions on “Bead Sort”.

1. Bead sort is also known as _________
a) gravity sort
b) strand sort
c) abacus sort
d) counting sort
Answer: a
Clarification: Bead sort is also known as gravity sort. It is because this algorithm was designed by keeping the natural phenomenon of falling objects in mind.

2. Which of the following sorting algorithm was inspired by the natural phenomenon of falling objects?
a) bogo sort
b) heap sort
c) bead sort
d) strand sort
Answer: c
Clarification: The algorithm of bead sort was inspired by the natural phenomenon of falling objects. Thus, it is also known by the name of gravity sort.

3. Which of the following sorting algorithm is only applicable to positive integers?
a) quick sort
b) heap sort
c) bead sort
d) strand sort
Answer: c
Clarification: Bead sort algorithm is only applicable to positive integers. This is because it works by placing number of beads equal to key value, in each row.

4. What is the auxiliary space complexity of bead sort?
a) O(n)
b) O(1)
c) O(n²)
d) O(n log n)
Answer: c
Clarification: The auxiliary space complexity of bead sort is O(n²). It is because an array of size maximum_element*n (maximum_element is the maximum element that is present in the array and n is the size of the array) has to be maintained.

5. Which of the following sorting algorithm is not in place?
a) quick sort
b) bead sort
c) cycle sort
d) heap sort

Answer: b
Clarification: Bead sort has an auxiliary space complexity of O(n2). So it is not an in place sorting algorithm.

6. Bead sort is a comparison based sorting algorithm.
a) true
b) false

Answer: b
Clarification: Bead sort is an example of non comparison based sorting algorithm. This is because it does not compare the value of elements present in a list in order to sort them.

7. How many comparisons will be required to sort the array arr={5, 4, 7, 1, 9} using bead sort?
a) 5
b) 4
c) 6
d) 0

Answer: d
Clarification: Bead sort is an example of a non-comparison based sorting algorithm. So no comparison is required to be performed in order to sort the array.

8. What is the average time complexity of bead sort (S = sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Average case time complexity of bead sort is O(S). It is because we drop each bead as a separate operation.

9. What is the best case time complexity of bead sort (S = sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: a
Clarification: Best case time complexity of bead sort is O(n). It is when a row of beads is dropped as a distinct operation and since the number of rows is equal to n.

10. What is the worst case time complexity of bead sort (S= sum of input elements)?
a) O(n)
b) O(S)
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Worst case time complexity of bead sort is O(S). It is because we drop each bead as a separate operation.

11. Which of the following code fragment puts sorted values in an array using beads correctly?
a)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max; j++); 
        //max is the maximum value element of given array a[]  
        a[i] = j; 
i}

b)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
        //max is the maximum value element of given array a[]
        a[i] = j; 
}

c)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

d)

for (int i = 0; i < n; i++) 
{ 
         int j;
        for (j = 0; j < max && beads[i * max + j]; j++); 
       //max is the maximum value element of given array a[]  
        a[j] = i; 
}

Answer: b
Clarification: After sorting the elements in the bead array we finally need to shift them to the original array. So we need to apply the condition j < max && beads[i * max + j] in order to achieve this.

12. Bead sort is only applicable to positive integers.
a) true
b) false

Answer: a
Clarification: Bead sort algorithm is only applicable to positive integers. This is because it works by placing the number of beads equal to key value, in each row.

and Answers.