Lesson test: Quicksort and selection

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.

Quicksort and selection

1.[2p]
Lomuto partitioning of an array of 8 elements makes how many comparisons?

CorrectNot quite: 7

2.[3p]
A textbook quicksort that always takes the last element as pivot is quadratic on

already sorted input, because the pivot is the maximum every time

Correct

randomly ordered input

The answer is: already sorted input, because the pivot is the maximum every time

input with no duplicate values

The answer is: already sorted input, because the pivot is the maximum every time

input whose length is a power of two

The answer is: already sorted input, because the pivot is the maximum every time

3.[3p]
Using $C (n) = 2 (n + 1) H_{n} - 4 n$ with $H_{1000} = 7.485$ , how many comparisons does quicksort average on 1000 elements?

CorrectNot quite: 10986

4.[3p]
Quicksort averages about 39 per cent more comparisons than mergesort's worst case and is still usually faster because

it moves far less data, allocates nothing, and scans memory sequentially

Correct

comparisons are free on modern hardware

The answer is: it moves far less data, allocates nothing, and scans memory sequentially

its recursion is shallower

The answer is: it moves far less data, allocates nothing, and scans memory sequentially

it is stable and mergesort is not

The answer is: it moves far less data, allocates nothing, and scans memory sequentially

5.[3p]
Choosing the pivot uniformly at random changes the analysis because

the expected cost no longer depends on the arrangement of the input at all

Correct

it removes the worst case entirely

The answer is: the expected cost no longer depends on the arrangement of the input at all

it makes the algorithm stable

The answer is: the expected cost no longer depends on the arrangement of the input at all

random numbers are cheaper to compute than a median of three

The answer is: the expected cost no longer depends on the arrangement of the input at all

6.[2p]
Median-of-three pivot selection guarantees that quicksort avoids its quadratic case.

True

The answer is: False

False

Correct

7.[2p]
Introsort achieves a worst-case $Θ (n \log n)$ bound by

switching to heapsort once the recursion depth exceeds about $2 \log_{2} n$

Correct

randomising the pivot on every call

The answer is: switching to heapsort once the recursion depth exceeds about $2\log_2 n$

merging the two halves instead of partitioning

The answer is: switching to heapsort once the recursion depth exceeds about $2\log_2 n$

sorting the smaller side first

The answer is: switching to heapsort once the recursion depth exceeds about $2\log_2 n$

8.[3p]
Quickselect is $Θ (n)$ on average rather than $Θ (n \log n)$ because

it recurses into one side only, so the level costs form a geometric series summing to under $2 n$

Correct

partitioning is cheaper than in quicksort

The answer is: it recurses into one side only, so the level costs form a geometric series summing to under $2n$

it needs no comparisons after the first partition

The answer is: it recurses into one side only, so the level costs form a geometric series summing to under $2n$

the pivot is always the median

The answer is: it recurses into one side only, so the level costs form a geometric series summing to under $2n$

9.[3p]
Match each algorithm to its worst-case cost.

Mergesort
Randomised quicksort
Introsort
Median-of-medians selection

$Θ (n \log n)$
$Θ (n \log n)$
$Θ (n)$
$Θ (n^{2})$

Show the answer

Mergesort: $Θ (n \log n)$ Randomised quicksort: $Θ (n^{2})$ Introsort: $Θ (n \log n)$ Median-of-medians selection: $Θ (n)$

1.[2p] Lomuto partitioning of an array of 8 elements makes how many comparisons?

2.[3p] A textbook quicksort that always takes the last element as pivot is quadratic on

3.[3p] Using C(n)=2(n+1)Hn-4n with H1000=7.485, how many comparisons does quicksort average on 1000 elements?

4.[3p] Quicksort averages about 39 per cent more comparisons than mergesort's worst case and is still usually faster because

5.[3p] Choosing the pivot uniformly at random changes the analysis because

6.[2p] Median-of-three pivot selection guarantees that quicksort avoids its quadratic case.

7.[2p] Introsort achieves a worst-case Θ(nlogn) bound by

8.[3p] Quickselect is Θ(n) on average rather than Θ(nlogn) because

9.[3p] Match each algorithm to its worst-case cost.

1.[2p]
Lomuto partitioning of an array of 8 elements makes how many comparisons?

2.[3p]
A textbook quicksort that always takes the last element as pivot is quadratic on

3.[3p]
Using $C (n) = 2 (n + 1) H_{n} - 4 n$ with $H_{1000} = 7.485$ , how many comparisons does quicksort average on 1000 elements?

4.[3p]
Quicksort averages about 39 per cent more comparisons than mergesort's worst case and is still usually faster because

5.[3p]
Choosing the pivot uniformly at random changes the analysis because

6.[2p]
Median-of-three pivot selection guarantees that quicksort avoids its quadratic case.

7.[2p]
Introsort achieves a worst-case $Θ (n \log n)$ bound by

8.[3p]
Quickselect is $Θ (n)$ on average rather than $Θ (n \log n)$ because

9.[3p]
Match each algorithm to its worst-case cost.