Engineering Questions with Answers - Multiple Choice Questions

# Bead Sort Multiple Choice MCQ

1 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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.

6 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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