Thu, 20 Oct 2011, 01:26

To my students in 306,

A few of my TAs expressed concern that some of you were having trouble with
Programming Lab 2 because you are unfamiliar with sorting.  I agreed to send 
you all this email, and they will talk more about it during the discussion 
sections on Friday.

"Sorting" is the computer word for "arranging in order."  You are all familiar
with sorting, although perhaps not in a formal way.  When you play cards (bridge,
for example), you are dealt 13 cards, which you immediately sort before play
begins.  The Dictionary sorts words according to "alphabetical order."  We often
sort grades according to "numerical order."  All three examples show that it is
much easier to operate with the data if it is first sorted.  It would be pretty
time consuming to look up a word in a dictionary if the words were not in
alphabetical order!

There are dozens of algorithms for sorting, some more complicated than others,
some faster than others.  This email is not going to be a complete tutorial on
sorting.  You will have to wait for EE 422C and EE 360C for that.  What I will
do, however, is describe one very simple sorting algorithm which you can use
to put the 16 grades into numerical order, the highest grade in x4000, the
lowest grade in x400F.  It is called the Selection Sort.

It works like this:

Initially, for example, the grades look like this:

x3200: 75                        x4000:
x3201: 69                        x4001:
x3202: 28                        x4002:
x3203: 45                        x4003:
x3204: 46                        x4004:
x3205: 47                        x4005:
x3206: 97                        x4006:
x3207: 91                        x4007:
x3208: 98                        x4008:
x3209: 52                        x4009:
x320A: 73                        x400A:
x320B: 21                        x400B:
x320C: 88                        x400C:
x320D: 60                        x400D:
x320E: 65                        x400E:
x320F: 84                        x400F:

Repeat the following process:

1. Find the highest score.  How would you do that?  How about loading a register
with the first score, in this case 75 (the contents of x3200).  You also might
want to load another register with the address (i.e., x3200). Now you compare
75 with every score until you find one that is bigger.  In x3206 you find a 97.
Thus you replace the 75 with 97 in the register and put x3206 into the other 
register.  After you have made all 16 comparisons, you have the highest score 
and which location it was in.  So, you store that value into x4000 and store -1
into the location where you found it.  Why do you suppose you store -1 in 
location x3208.  Your memory locations now looks like this:


x3200: 75                        x4000: 98
x3201: 69                        x4001:
x3202: 28                        x4002:
x3203: 45                        x4003:
x3204: 46                        x4004:
x3205: 47                        x4005:
x3206: 97                        x4006:
x3207: 91                        x4007:
x3208: -1                        x4008:
x3209: 52                        x4009:
x320A: 73                        x400A:
x320B: 21                        x400B:
x320C: 88                        x400C:
x320D: 60                        x400D:
x320E: 65                        x400E:
x320F: 84                        x400F:

Start at the top again, and repeat the process, this time ending up with putting
the highest score into x4001, and -1 in the location where you found it.  You 
will need a register to keep track of where the result from each iteration of 
the loop is to be stored.

After 16 iterations of the loop, you will have the grades sorted in x4000 to
x400F.  Note that each iteration requires making 15 comparisons.  Thus, in
executing each of the 16 iterations of the loop, you perform another loop body 
15 times.  We call such a structure a nested loop.

I hope the above helps.  Feel free to ask the TAs questions about this on
Friday and in office hours.

Good luck finishing the program by Sunday night.

Yale Patt