Sorting

* Definition: Sorting means to put data in order;
either numerically or alphabetically.

There are many times when it is necessary to put an array in order from highest to lowest (descending) or lowest to highest (ascending).  Because sorting arrays requires exchanging values, computers must use a special technique to swap the positions of array elements so as not to lose any elements.
Will this work to swap the values x and y?
Nope!
 x = y; y = x;
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 can NOT just do this:
grade[1] = grade[2];
grade[2] = grade[1];
// Does NOT Work!!

In the first line, the value of 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! What happened to the value in grade[1]?  It is lost!!!!

A temporary holding variable is needed for swapping values.

 temp = x; x = y; y = temp; temp = a[ i ]; a[ i ] = a[ j ] a[ j ] = temp;
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];
// place in holding variable
grade[1] = grade[2];
grade[2] = temp;   // get value from holding variable

This process successfully exchanges ("swaps") the values of the two variables,
without the loss of any values.

Consider this example of two horses switching stalls!

 Consider this scenario   You have a boy horse (a stallion) in one stall and a girl horse (a mare) in another.  You can tell the girl horse by her fancy clothing!  Your task is to single-handedly switch the horses, having contact with only one horse at a time.  We do not want the stallion and the mare in the same stall at the same time because we do not want any "baby" horses.  How are you going to accomplish this task? A "temporary holding stall" is the answer!

Ways to sort arrays:

There are many different ways to sort arrays. The basic goal of each method is to compare each array element to another array element and swap them if they are in the wrong position.

 Teachers:  When attempting to illustrate the swapping process in various sorting algorithms, use laminated number cards with craft magnets on the back.  As you step through the sorting code, you (or a student volunteer) can appropriately maneuver the numbers, thus illustrating the workings of the sort.  It is particularly useful to show that one iteration of a loop does not necessarily complete the swapping process.