Which of followings are true or false? a. Swapping two adjacent elements that are out of place removes only one inversion.
b. Any algorithm that sorts by exchanging adjacent elements requires O(n log n)
c. Shellsort with a proper distance function is faster than mergesort for a very large input (like sorting 1 billion numbers).
d. The average-case performance of quick sort is O(NlogN), but the best-case performance of quick sort is O(N) for a pre-sorted input.
e. The number of leaves in a decision tree for sorting n numbers by comparisons must be 2n.
f. The height of a decision tree for sorting gives the minimum number of comparisons in the best case.
g. Any decision tree that can sort n elements must have height Big-Omega (n log n).
h. Bucket-sort can be modeled by a decision tree.

Explanation:

a. Swapping two adjacent elements that are out of place removes only one inversion.

True

b. Any algorithm that sorts by exchanging adjacent elements requires O(n log n)

False

c. Shellsort with a proper distance function is faster than mergesort for a very large input (like sorting 1 billion numbers).

True

d. The average-case performance of quick sort is O(NlogN), but the best-case performance of quick sort is O(N) for a pre-sorted input.

True

e. The number of leaves in a decision tree for sorting n numbers by comparisons must be 2n.

False

f. The height of a decision tree for sorting gives the minimum number of comparisons in the best case.

True

g. Any decision tree that can sort n elements must have height Big-Omega (n log n).

h. Bucket-sort can be modeled by a decision tree.

True

answer; peter zenger;