Java Reference
In-Depth Information
special niche applications (Heapsort). Sorting provides an example of a significant
technique for analyzing the lower bound for a problem. Sorting will also be used
to motivate the introduction to file processing presented in Chapter 8.
The present chapter covers several standard algorithms appropriate for sorting
a collection of records that fit in the computer's main memory. It begins with a dis-
cussion of three simple, but relatively slow, algorithms requiring (n
2
) time in the
average and worst cases. Several algorithms with considerably better performance
are then presented, some with (n log n) worst-case running time. The final sort-
ing method presented requires only (n) worst-case time under special conditions.
The chapter concludes with a proof that sorting in general requires (n log n) time
in the worst case.
7.1
Sorting Terminology and Notation
Except where noted otherwise, input to the sorting algorithms presented in this
chapter is a collection of records stored in an array. Records are compared to
one another by requiring that their type extend the
Comparable
class. This will
ensure that the class implements the
compareTo
method, which returns a value
less than zero, equal to zero, or greater than zero depending on its relationship to
the record being compared to. The
compareTo
method is defined to extract the
appropriate key field from the record. We also assume that for every record type
there is a
swap
function that can interchange the contents of two records in the
array.
Given a set of records r
1
, r
2
, ..., r
n
with key values k
1
, k
2
, ..., k
n
, the Sorting
Problem is to arrange the records into any order s such that records r
s
1
, r
s
2
, ..., r
s
n
have keys obeying the property k
s
1
k
s
2
::: k
s
n
. In other words, the sorting
problem is to arrange a set of records so that the values of their key fields are in
non-decreasing order.
As defined, the Sorting Problem allows input with two or more records that have
the same key value. Certain applications require that input not contain duplicate
key values. The sorting algorithms presented in this chapter and in Chapter 8 can
handle duplicate key values unless noted otherwise.
When duplicate key values are allowed, there might be an implicit ordering
to the duplicates, typically based on their order of occurrence within the input. It
might be desirable to maintain this initial ordering among duplicates. A sorting
algorithm is said to be stable if it does not change the relative ordering of records
with identical key values. Many, but not all, of the sorting algorithms presented in
this chapter are stable, or can be made stable with minor changes.
When comparing two sorting algorithms, the most straightforward approach
would seem to be simply program both and measure their running times. An ex-
ample of such timings is presented in Figure 7.20. However, such a comparison
