0.3 Sorting Algorithms
Several common sorting algorithms are discussed in the following
section along with a careful examination of the strengths and
weaknesses of each.
Before any discussion of sorting, however, it is useful to define some
terms which will be used in describing the process or sorting. A sorting algorithm is one orders a data set based on some key
value. A particular data set comprised of n items can have
anywhere between one and n distinct (or ``unique'') keys. For
example, a set in which all the items are identical would only have
one key and is said to be a homogeneous set. A set with a few
identical items might have (n - x) keys where x is the number of
identical items in said set.
All sorting algorithms can be divided into one of two categories:
those which are comparison based
and those which are not. A comparison based algorithm is one that
orders the data set by weighing the key value of one element against
that of one or many other elements. Conversely a non comparison
based
sort puts the target data set into order without consideration of two
or more data items.
The efficiency of each presented algorithm is discussed in detail.
When considering the efficiency of a given algorithm it is useful to
examine its performance in several cases. These include sorting data
sets of various sizes, data sets already in sorted order, data sets in
reverse sorted order, and data sets in random order. Sometimes the
number of comparisons performed by a particular algorithm does not
matter but the number of swaps must be minimized because swapping
records is expensive. Other we need not worry about space but
want an algorithm that sorts as quickly as possible. It is vital to know something about the data which you are sorting in order
to choose the algorithm that best matches your needs.
In the following sections we explore the following algorithms in
detail:
| 
Search