Java Reference
In-Depth Information
can be misleading because the running time for many sorting algorithms depends
on specifics of the input values. In particular, the number of records, the size of
the keys and the records, the allowable range of the key values, and the amount by
which the input records are “out of order” can all greatly affect the relative running
times for sorting algorithms.
When analyzing sorting algorithms, it is traditional to measure the number of
comparisons made between keys. This measure is usually closely related to the
running time for the algorithm and has the advantage of being machine and data-
type independent. However, in some cases records might be so large that their
physical movement might take a significant fraction of the total running time. If so,
it might be appropriate to measure the number of swap operations performed by the
algorithm. In most applications we can assume that all records and keys are of fixed
length, and that a single comparison or a single swap operation requires a constant
amount of time regardless of which keys are involved. Some special situations
“change the rules” for comparing sorting algorithms. For example, an application
with records or keys having widely varying length (such as sorting a sequence of
variable length strings) will benefit from a special-purpose sorting technique. Some
applications require that a small number of records be sorted, but that the sort be
performed frequently. An example would be an application that repeatedly sorts
groups of five numbers. In such cases, the constants in the runtime equations that
are usually ignored in an asymptotic analysis now become crucial. Finally, some
situations require that a sorting algorithm use as little memory as possible. We will
note which sorting algorithms require significant extra memory beyond the input
array.
7.2
Three
(n
2
)
Sorting Algorithms
This section presents three simple sorting algorithms. While easy to understand
and implement, we will soon see that they are unacceptably slow when there are
many records to sort. Nonetheless, there are situations where one of these simple
algorithms is the best tool for the job.
7.2.1
Insertion Sort
Imagine that you have a stack of phone bills from the past two years and that you
wish to organize them by date. A fairly natural way to do this might be to look at
the first two bills and put them in order. Then take the third bill and put it into the
right order with respect to the first two, and so on. As you take each bill, you would
add it to the sorted pile that you have already made. This naturally intuitive process
is the inspiration for our first sorting algorithm, called Insertion Sort. Insertion
Sort iterates through a list of records. Each record is inserted in turn at the correct
position within a sorted list composed of those records already processed.
The
