Lesson test: The limits of sorting

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

The limits of sorting

1.[3p]
Why must a correct comparison sort of $n$ distinct elements have at least $n!$ leaves in its decision tree?

Two inputs that answer every comparison the same way reach the same leaf and get the same output, so each of the $n!$ permutations needs its own leaf

Correct

Because $n!$ is the number of comparisons it makes

The answer is: Two inputs that answer every comparison the same way reach the same leaf and get the same output, so each of the $n!$ permutations needs its own leaf

Because every internal node has exactly two children

The answer is: Two inputs that answer every comparison the same way reach the same leaf and get the same output, so each of the $n!$ permutations needs its own leaf

Because the tree must be balanced

The answer is: Two inputs that answer every comparison the same way reach the same leaf and get the same output, so each of the $n!$ permutations needs its own leaf

2.[2p]
What is the smallest number of comparisons that could sort six elements, from the counting bound? Give a whole number.

CorrectNot quite: 10

3.[3p]
Using $\log_{2} (n!) \approx n \log_{2} n - 1.4427 n$ , roughly how many comparisons are needed at minimum to sort a million elements? Give the answer in millions.

CorrectNot quite: 18.5

4.[2p]
The bound $\log_{2} (n!)$ is always achievable, so 29 comparisons suffice to sort twelve elements.

True

The answer is: False

False

Correct

5.[3p]
Which of these are true of the $n \log n$ lower bound?

Select all that apply

It applies to the average case as well as the worst case

Correct

It says nothing about algorithms that use a key as an array index

Correct

Insertion sort finishing in $n - 1$ comparisons on sorted input does not contradict it

Correct

It proves that no sorting algorithm can run in linear time on any input

The answer is: It applies to the average case as well as the worst case, It says nothing about algorithms that use a key as an array index, Insertion sort finishing in $n-1$ comparisons on sorted input does not contradict it

6.[2p]
Counting-sorting 40 keys drawn from the range 0 to 9 costs about $n + k$ operations. What is that total?

CorrectNot quite: 50

7.[3p]
Radix sort would break if its per-digit pass were not stable because

ties on the current digit must keep the order established by the lower digits already sorted

Correct

the counters would overflow

The answer is: ties on the current digit must keep the order established by the lower digits already sorted

it would need more passes

The answer is: ties on the current digit must keep the order established by the lower digits already sorted

the highest digit would be processed first

The answer is: ties on the current digit must keep the order established by the lower digits already sorted

8.[3p]
Put these arrays in the order radix sort produces them, starting from 213, 902, 130, 921, 013, 900.

013, 130, 213, 900, 902, 921
130, 900, 921, 902, 213, 013
900, 902, 213, 013, 921, 130

Show the answer

b, a, c

9.[3p]
Match each non-comparison sort to the assumption it needs.

Counting sort
Radix sort
Bucket sort
Comparison sort

nothing beyond an ordering
keys splittable into fixed-width digits
a key range small enough to index
keys spread evenly over the range

Show the answer

Counting sort: a key range small enough to index Radix sort: keys splittable into fixed-width digits Bucket sort: keys spread evenly over the range Comparison sort: nothing beyond an ordering

1.[3p] Why must a correct comparison sort of n distinct elements have at least n! leaves in its decision tree?

2.[2p] What is the smallest number of comparisons that could sort six elements, from the counting bound? Give a whole number.

3.[3p] Using log2(n!)≈nlog2n-1.4427n, roughly how many comparisons are needed at minimum to sort a million elements? Give the answer in millions.

4.[2p] The bound log2(n!) is always achievable, so 29 comparisons suffice to sort twelve elements.

5.[3p] Which of these are true of the nlogn lower bound?

6.[2p] Counting-sorting 40 keys drawn from the range 0 to 9 costs about n+k operations. What is that total?

7.[3p] Radix sort would break if its per-digit pass were not stable because

8.[3p] Put these arrays in the order radix sort produces them, starting from 213, 902, 130, 921, 013, 900.

9.[3p] Match each non-comparison sort to the assumption it needs.

1.[3p]
Why must a correct comparison sort of $n$ distinct elements have at least $n!$ leaves in its decision tree?

2.[2p]
What is the smallest number of comparisons that could sort six elements, from the counting bound? Give a whole number.

3.[3p]
Using $\log_{2} (n!) \approx n \log_{2} n - 1.4427 n$ , roughly how many comparisons are needed at minimum to sort a million elements? Give the answer in millions.

4.[2p]
The bound $\log_{2} (n!)$ is always achievable, so 29 comparisons suffice to sort twelve elements.

5.[3p]
Which of these are true of the $n \log n$ lower bound?

6.[2p]
Counting-sorting 40 keys drawn from the range 0 to 9 costs about $n + k$ operations. What is that total?

7.[3p]
Radix sort would break if its per-digit pass were not stable because

8.[3p]
Put these arrays in the order radix sort produces them, starting from 213, 902, 130, 921, 013, 900.

9.[3p]
Match each non-comparison sort to the assumption it needs.