next up previous contents index Search
Next: 0.3.1 The Quicksort Up: Algorithm Archive (Work in Previous: Octree Source Code

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:

Scott Gasch