10/24/2006

A student writes:

        Dr. Patt,

        Upon reading the second programming assignment, I immediately 
        thought to use the bubble sort algorithm to solve the problem. 
        However, I can't help but wonder if there is a more efficient 
        way of solving the problem. I'm not looking for any explanation, 
        but a simple answer. Is there a way to be more
        efficient than the bubble sort? The selection sort possibly?

        Thank you,

        <<name withheld to protect the student who is looking forward to 322C>>

I talked about this a little in class today.  I will expand.

Yes, there are lots and lots of sorting algorithms, and which is best
depends on a lot of things, including (1) whether or not all the data 
to be sorted can be in memory at the same time, (2) how many processors 
we have available to use on the problem simultaneously, and (3) how 
complicated we wish to make the sorting algorithm.  In fact, my hero 
in this business is Donald E. Knuth, who started writing his amazing 
tome, "The Art of Computer Programming," more than 40 years ago.  
Volume 3 contains about 300 pages on sorting, and you are welcome to 
check it out of the library.

Meanwhile, we are here now in ee306, where I thought you might prefer to
use a very simple algorithm.  So, sure you can use Bubble Sort.  ...or,
Heap Sort, or Quiksort, or Merge Sort, or whatever sort.  ...as long as 
you program it in LC-3 Assembly Language, AND you get it to work.

The Hints try to lead you to a simpler algorithm, which should be easier
to program and easier to get it to work.

Good luck.
Yale Patt