MathBits.com
Return to Unit Menu | Java Main Page | MathBits.com | Terms of Use  
 

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.


Return to Unit Menu | Java Main Page | MathBits.com | Terms of Use