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

This proof is an example of a lower-bound proof. It is valid not only for
the insertion sort, which performs adjacent exchanges implicitly, but also for
other simple algorithms such as the bubble sort and the selection sort, which
we do not describe here. In fact, it is valid over an entire class of algorithms,
including undiscovered ones, that perform only adjacent exchanges.
Unfortunately, any computational confirmation of a proof applying to a
class of algorithms would require running all algorithms in the class. That is
impossible because there are infinitely many possible algorithms. Hence any
attempt at confirmation would apply only to the algorithms that are run. This
restriction makes the confirmation of the validity of lower-bound proofs more
difficult than the usual single-algorithm upper bounds that we are accustomed
to. A computation could only disprove a lower-bound conjecture; it could
never prove it in general.
Although this lower-bound proof is rather simple, proving lower bounds is
in general much more complicated than proving upper bounds. Lower-bound
arguments are much more abstract than their upper-bound counterparts.
This lower bound shows us that, for a sorting algorithm to run in subqua-
dratic or o ( N 2 ) time, it must make comparisons and, in particular, exchanges
between elements that are far apart. A sorting algorithm progresses by elimi-
nating inversions. To run efficiently, it must eliminate more than just one
inversion per exchange.

The lower-bound
proof shows that
quadratic perfor-
mance is inherent
in any algorithm
that sorts by per-
forming adjacent
comparisons.

shellsort

8.4

The first algorithm to improve on the insertion sort substantially was
Shellsort, which was discovered in 1959 by Donald Shell. Though it is not the
fastest algorithm known, Shellsort is a subquadratic algorithm whose code is
only slightly longer than the insertion sort, making it the simplest of the faster
algorithms.
Shell's idea was to avoid the large amount of data movement, first by
comparing elements that were far apart and then by comparing elements that
were less far apart, and so on, gradually shrinking toward the basic insertion
sort. Shellsort uses a sequence called the increment sequence.
Any increment sequence will do as long as h 1 = 1, but some choices are bet-
ter than others. After a phase, using some increment h k , we have
for every i where i + h k is a valid index; all elements spaced
h k apart are sorted. The array is then said to be h k -sorted.
For example, Figure 8.5 shows an array after several phases of Shellsort.
After a 5-sort, elements spaced five apart are guaranteed to be in correct
sorted order. In the figure, elements spaced five apart are identically shaded

Shellsort is a sub-
quadratic algorithm
that works well in
practice and is sim-
ple to code. The
performance of
Shellsort is highly
dependent on the
increment
sequence and
requires a challeng-
ing (and not com-
pletely resolved)
analysis.

h 1 h 2 , , … , h t

ai [] ≤ ai h k [ + ]