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