Java Reference
In-Depth Information
InsertionBubbleSelection
Comparisons:
Best Case
(n
2
)
(n
2
)
(n)
(n
2
)
(n
2
)
(n
2
)
Average Case
(n
2
)
(n
2
)
(n
2
)
Worst Case
Swaps:
Best Case
0
0
(n)
(n
2
)
(n
2
)
Average Case
(n)
(n
2
)
(n
2
)
Worst Case
(n)
Figure7.5
A comparison of the asymptotic complexities for three simple sorting
algorithms.
array must move to reach their “correct” location (i.e., the number of inversions for
each record).
What is the average number of inversions? Consider a list L containing n val-
ues. Define L
R
to be L in reverse. L has n(n1)=2 distinct pairs of values, each of
which could potentially be an inversion. Each such pair must either be an inversion
in L or in L
R
. Thus, the total number of inversions in L and L
R
together is exactly
n(n1)=2 for an average of n(n1)=4 per list. We therefore know with certainty
that any sorting algorithm which limits comparisons to adjacent items will cost at
least n(n 1)=4 = (n
2
) in the average case.
7.3
Shellsort
The next sorting algorithm that we consider is called Shellsort, named after its
inventor, D.L. Shell. It is also sometimes called the diminishing increment sort.
Unlike Insertion and Selection Sort, there is no real life intuitive equivalent to Shell-
sort. Unlike the exchange sorts, Shellsort makes comparisons and swaps between
non-adjacent elements. Shellsort also exploits the best-case performance of Inser-
tion Sort. Shellsort's strategy is to make the list “mostly sorted” so that a final
Insertion Sort can finish the job. When properly implemented, Shellsort will give
substantially better performance than (n
2
) in the worst case.
Shellsort uses a process that forms the basis for many of the sorts presented
in the following sections: Break the list into sublists, sort them, then recombine
the sublists. Shellsort breaks the array of elements into “virtual” sublists. Each
sublist is sorted using an Insertion Sort. Another group of sublists is then chosen
and sorted, and so on.
During each iteration, Shellsort breaks the list into disjoint sublists so that each
element in a sublist is a fixed number of positions apart. For example, let us as-
sume for convenience that n, the number of values to be sorted, is a power of two.
One possible implementation of Shellsort will begin by breaking the list into n=2
