Final answer:
The true statements about sorting algorithms are that bucket sort is not a comparison sort, and radix sort is stable. Other statements regarding the number of leaves in a decision tree for comparison sorts and the assertion that every sorting algorithm is O(n) or that insertion sort is asymptotically optimal are false.
Step-by-step explanation:
The student has asked which of the statements a, b, c, d, e, and f are true when it comes to sorting algorithms. Here's the explanation for each statement:
- a. False: The number of leaves in the decision tree of a comparison sort is not 12 (n!), but rather just n!. This represents all possible permutations of the n elements to be sorted.
- b. False: Any comparison sort algorithm does not necessarily require 2(n log n) comparisons in the worst case. The number of comparisons needed in the worst case for any comparison sort is actually Ω(n log n), which is the lower bound. Certain sorts may have worse complexity.
- c. True: Bucket sort is not a comparison sort. It falls under the category of distribution sort, which works by distributing the elements of an array into a number of buckets.
- d. False: Not every sorting algorithm has a running time of O(n). Some have better or worse running times depending on the algorithm and size of n.
- e. False: Insertion sort is not asymptotically optimal; it runs in O(n^2) time in the average and worst case, whereas the best case is O(n).
- f. True: Radix sort is indeed a stable sort meaning that it maintains the relative order of equal elements.
Therefore, the true statements from the ones given are c (Bucket sort is not a comparison sort) and f (Radix sort is stable).