Data Structures & Algorithms Multiple Choice Questions on “Strand Sort”.
1. Which one of the following sorting algorithm requires recursion?
a) pigeonhole sort
b) strand sort
c) insertion sort
d) counting sort
Answer: b
Clarification: Strand sort requires the use of recursion for implementing its algorithm. On the other hand, the sorting algorithms given in the remaining options use iterative methods.
2. Strand sort is most efficient for data stored in?
a) linked list
b) arrays
c) trees
d) graphs
Answer: a
Clarification: Strand sort is most efficient when data is stored in a linked list as it involves many insertions and deletions which is performed quite efficiently with the help of a linked list. Using an array would increase time complexity significantly.
3. In which of the following case strand sort is most efficient? Answer: a 4. What is the auxiliary space complexity of strand sort? Answer: a 5. Which of the following sorting algorithm is not in place? Answer: b 6. Strand sort is a comparison based sorting algorithm. 7. Strand sort is a stable sorting algorithm. Answer: a 8. What is the average time complexity of strand sort? Answer: c 9. What is the best case time complexity of strand sort? Answer: a 10. What is the worst case time complexity of strand sort? Answer: c 11. Strand sort algorithm used which of the following method for sorting a list? Answer: b 12. Which of the following is an adaptive sorting algorithm? Answer: b
a) when input array is already sorted
b) when input array is reverse sorted
c) when input array is large
d) when input array is has randomly spread elements
Clarification: The best case of strand sort occurs when the input array is already sorted. In this case, it has linear time complexity.
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
Clarification: The auxiliary space complexity of strand sort is O(n). It is because a sub-list of size n has to be maintained.
a) quick sort
b) strand sort
c) cycle sort
d) heap sort
Clarification: Strand sort has an auxiliary space complexity of O(n). So it is not an in place sorting algorithm.
a) true
b) false
Answer: a
Clarification: Pigeonhole sort is an example of a comparison based sorting algorithm. This is because it compares the value of elements present in a list in order to sort them.
a) true
b) false
Clarification: Strand sort is an example of a stable sorting algorithm. It is because the elements with identical values appear in the same order in the output array as they were in the input array.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Clarification: Average case time complexity of strand sort is O(n2). So it is not as efficient as quick sort or merge sort.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Clarification: Best case time complexity of strand sort is O(n). It occurs in the case where the input array is already sorted.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Clarification: Worst case time complexity of strand sort is O(n2). It occurs in the case where the input array is in reverse sorted order.
a) merging
b) selection
c) insertion
d) partitioning
Clarification: Strand sort uses the method of selection for sorting any given list. This is because it selects the strands of elements from the input list which are sorted.
a) heap sort
b) strand sort
c) selection sort
d) merge sort
Clarification: Strand sort is an adaptive sorting algorithm. This is because it gives a better performance when the input list is almost sorted.