Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Aeronautical Engineering » Bead Sort Multiple Choice MCQ

# Bead Sort Multiple Choice MCQ

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.

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.

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.

What is the auxiliary space complexity of bead sort?

a) O(n)

b) O(1)

c) O(n^{2})

d) O(n log n)

**
View Answer**

Answer: c

Explanation: The auxiliary space complexity of bead sort is O(n^{2}). 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.

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.

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.

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.

What is the average time complexity of bead sort (S = sum of input elements)?

a) O(n)

b) O(S)

c) O(n^{2})

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.

What is the best case time complexity of bead sort (S = sum of input elements)?

a) O(n)

b) O(S)

c) O(n^{2})

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.

What is the worst case time complexity of bead sort (S= sum of input elements)?

a) O(n)

b) O(S)

c) O(n^{2})

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.

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.

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.