(Up to Basic
Computer Science : Lists and Arrays)
Sorting has been analyzed by computer scientists for decades,
and thus it is an ideal subject to begin with when studying computer
science. Sorting is done with algorithms, which are a set
of specific commands that are followed in a certain order to complete
a task. A cooking recipe is an algorithm, but we usually reserve
the word algorithm for mathematics or science related topics.
To study sorting, you must first be comfortable with iteration
and recursion. These two terms designate the ways tasks are
repeatedly performed. A jolly old programmer might give you this
definition of recursion:
re-cur-sion (ri-'ker-zhen) n See recursion.
If you don't know what iteration and recursion are and how they
are different, look up a book on a common programming language
like C++ and it should tell you. Or, you can go to Cprogramming.com,
which has tutorials on C++ with a section on recursion.
Note: in most of these algorithms, two elements of an array
are often switched. So, to make the algorithms easier to read, we
have written a function called swap()
which takes two variables and exchanges the values in them. Here
is the function code in C++:
inline int swap( int &x, int &y )
int z = x;
x = y;
y = z;
Note as well that we are using C++. For all the example
code in this site, we will be using C++, for it is a widely used
and taught language that is efficient and suitable for our purposes.
The basic sorting algorithms are mostly iterative, and thus
probably easier to understand.
The most simple algorithm, but not the most intuitive algorithm,
is Bubble sort. This sort is still used
a lot because it is easier and shorter to type than the other sorts.
The most intuitive algorithm is Selection
Sort. Humans use this sort all the time when sorting objects.
This algorithm is especially useful when sorting across a network.
Radix Sort (also known as Bin Sort)
is a fairly fast sort that uses digits of numbers to sort arrays.
Because of this, however, Radix Sort is fairly specialized, and
makes it difficult to write general purpose code.
A very important sorting algorithm is Insertion
Sort. This sort may not seem important, but it is used a surprising
amount because it works well with almost sorted arrays.
One of the advanced sorting algorithms is the Heap
Sort, which is based on the Heap
Tree. You should read the two essays on Data
Trees and Heap Trees before
you attempt to read about this sort.