Sorting Arrays

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 built-in 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, odd-even transposition sort, and the shear sort.  Shows comparisons of times to complete the sorts.