
Sorting Arrays
* Definition: Sorting is
the process of putting data in order;
either numerically or alphabetically.

It is often necessary to arrange the elements in an array in numerical order from highest to lowest
values (descending order) or vice versa (ascending
order). If the array contains string values, alphabetical order may
be needed (which is actually ascending order using ASCII values).
The process of sorting an array requires the exchanging of values.
While this seems to be a simple process, a computer must be careful that no
values are lost during this exchange. Consider the following dilemma:
Suppose that grade[1] = 10 and
grade[2] = 8 and you want to exchange their values so that
grade[1] = 8 and grade[2] = 10. You could
NOT just do this:
grade[1] = grade[2];
grade[2] = grade[1]; // DOES NOT WORK!!!
In the first step, the value stored in grade[1] is erased and replaced with
grade[2].
The result is that both grade[1] and
grade[2] now have the same value. Oops! Then what happened to
the value in grade[1]? It is lost!!!
In order to swap two values, you must use a third variable,
(a "temporary holding variable"), to
temporarily
hold the value you do not want to lose:
//swapping
variables
temp = grade[1];
// holding variable
grade[1] = grade[2];
grade[2] = temp;
This process successfully exchanges, "swaps", the values of the two variables
(without the loss of any values).
Remember the example in class of the two horses switching stalls!!
Ways to sort arrays:
There are literally hundreds of different ways to sort arrays. The basic goal of each
of these methods is the same: to compare each array element to another array element and swap them if they are in the wrong position.
The bubble sort is one of the easiest algorithms to understand and we will begin our investigation with this sort.
Click to see the codings of these various
algorithms:
Bubble Sort
Exchange Sort
Selection Sort
Insertion Sort
Shell Sort
Quick Sort
Merge Sort

There are often builtin search and sort "routines" in
various C++ compiler packages (such as bsearch, lfind, lsearch, and qsort).
These routines were not designed to be used with apvectors. The use of these routines also requires an understanding of "pointers", which we have not yet discussed.
It is imperative that you, the programmer, know and understand at least one method of searching an array and one method of sorting an array, separate from any built in "routines." 
Link to viewing animated
representations of sorting:

Sorting
Algorithms
java representations of bubble sort,
quick sort, oddeven transposition sort, and the shear sort. Shows
comparisons of times to complete the sorts.
