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

common errors

1. The sorts coded in this chapter begin at array position 0, not position 1.
2. Using the wrong increment sequence for Shellsort is a common error. Be
sure that the increment sequence terminates with 1 and avoid sequences
that are known to give poor performance.
3. Quicksort has many traps. The most common errors deal with sorted
inputs, duplicate elements, and degenerate partitions.
4. For small inputs an insertion sort is appropriate, but using it for large
inputs is wrong.

on the internet

All the sorting algorithms and an implementation of quickselect are in a single file.

Duplicate.java Contains the routine in Figure 8.1 and a test program.

Sort.java Contains all the sorting algorithms and the selection

algorithm.

exercises

IN SHORT
8.1

Sort the sequence 8, 1, 4, 1, 5, 9, 2, 6, 5 by using
a.

Insertion sort

b. Shellsort for the increments {1, 3, 5}

c. Mergesort

d. Quicksort, with the middle element as pivot and no cutoff (show

all steps)

e. Quicksort, with median-of-three pivot selection and a cutoff of 3

A sorting algorithm is stable if elements with equal keys are left in
the same order as they occur in the input. Which of the sorting algo-
rithms in this chapter are stable and which are not? Why?

8.2

Explain why the elaborate quicksort in the text is better than ran-
domly permuting the input and choosing the middle element as pivot.

8.3