Sorting algorithms - Data Structures and Problem Solving Using Java - page 386

IN THEORY
8.4

When all keys are equal, what is the running time of
a.

Insertion sort

b. Shellsort

c. Mergesort

d. Quicksort

When the input has been sorted, what is the running time of
a.

8.5

Insertion sort

b. Shellsort

c. Mergesort

d. Quicksort

When the input has been sorted in reverse order, what is the running
time of
a.

8.6

Insertion sort

b. Shellsort

c. Mergesort

d. Quicksort

8.7

Suppose that we exchange elements a[i] and a[i+k] , which were
originally out of order. Prove that at least 1 and at most 2 k - 1 inver-
sions are removed.

8.8

Construct a worst-case input for quicksort with
a. The middle element as pivot

b. Median-of-three pivot partitioning

8.9

Show that the quickselect algorithm has linear average performance.
Do so by solving Equation 8.5 with the constant 2 replaced by 1.

8.10

Using Stirling's formula, N ! Ne ≥ ( ⁄ )

N

2 π N , derive an estimate for

log ( N !).

Prove that any comparison-based algorithm used to sort four elements
requires at least five comparisons for some input. Then show that an
algorithm that sorts four elements using at most five comparisons
does indeed exist.

8.11

What is the worse-case number of comparisons used by mergesort to
sort six numbers? Is this optimal?

8.12

When implementing quicksort, if the array contains lots of duplicates,
you may find it best to perform a three-way partition (into elements less
than, equal to, and greater than the pivot) and make smaller recursive
calls. Assume that you can use three-way comparisons.

8.13