|
* 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!
|
|
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.
Click to see the coding for:
Bubble Sort
Exchange Sort
Selection Sort
Insertion Sort
Alphabetic Sort
Shell Sort
Quick Sort
Merge Sort
Built-In Sorting Routines
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. |
|
Return to Unit Menu | JavaBitsNotebook.com | MathBits.com | Terms
of Use | JavaMathBits.com
|
