|
 |
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 score[1] = 10 and
score[2] = 8 and you want to exchange their values so that
score[1] = 8 and score[2] = 10. You
can NOT just do this:
score[1] = score[2];
score[2] = score[1];
// Does NOT Work!! |
In the first line, the value of score[1] is
erased and replaced with
score[2].
The result is that both score[1] and score[2]
now have the same value.
You lost the original value that was in score[1].
|
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 to
temporarily hold the value you do not want to lose:
//swapping
variables
temp = score[1];
// holding variable
score[1] = score[2];
score[2] = temp; |
This process successfully exchanges the values of the two variables.
 |
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. |
 |
Links 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.
-
Animated
Sorts
shows the bubble sort, the insertion
sort, the merge sort, the quick sort, the selection sort, and the shell
sort. Scroll to the right to see the entire screen.
|
