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

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
d) strand sort

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
d) strand sort

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.

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

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
c) cycle sort
d) heap sort

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

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

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.

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)

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)

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.

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)

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]