Java Reference
In-Depth Information
chapter
8
S
orting is a fundamental application for computers. Much of the
output eventually produced by a computation is sorted in some way, and
many computations are made efficient by invoking a sorting procedure inter-
nally. Thus sorting is perhaps the most intensively studied and important oper-
ation in computer science.
In this chapter we discuss the problem of sorting an array of elements. We
describe and analyze the various sorting algorithms. The sorts in this chapter
can be done entirely in main memory, so the number of elements is relatively
small (less than a few million). Sorts that cannot be performed in main mem-
ory and must be done on disk or tape are also quite important. We discuss this
type of sorting, called
external sorting,
in Section 21.6.
This discussion of sorting is a blend of theory and practice. We present
several algorithms that perform differently and show how an analysis of an
algorithm's performance properties can help us make implementation deci-
sions that are not obvious.
In this chapter, we show
That simple sorts run in quadratic time
n
How to code Shellsort, which is a simple and efficient algorithm that
runs in subquadratic time
n
Search WWH ::
Custom Search