Bead Sort Multiple Choice Questions and Answers (MCQs)

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

1. Bead sort is also known as _________
a) gravity sort
b) strand sort
c) abacus sort
d) counting sort
View Answer

Answer: a
Explanation: 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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: c
Explanation: 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.
advertisement
advertisement

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

Answer: c
Explanation: The auxiliary space complexity of bead sort is O(n2). 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
View Answer

Answer: b
Explanation: Bead sort has an auxiliary space complexity of O(n2). So it is not an in place sorting algorithm.
Note: Join free Sanfoundry classes at Telegram or Youtube

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

Answer: b
Explanation: 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
View Answer

Answer: d
Explanation: 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.
advertisement

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

Answer: b
Explanation: 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(n2)
d) O(n log n)
View Answer

Answer: a
Explanation: 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.
advertisement

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

Answer: b
Explanation: 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; 
}
View Answer
Answer: b
Explanation: 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
View Answer

Answer: a
Explanation: 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.

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.