|
 |
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 vice versa (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];
// 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!
 |
Consider this scenario
(a favorite of my students):
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! |
(Teachers: laminated clip art with craft
magnets on the back become an instant teaching tools.)
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:
Bubble Sort
Exchange Sort
Selection Sort
Insertion Sort
Alphabetic Order 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. |
 |
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.
|
