Friday, October 23, 2009 4:13 AM,
A student asked me if I could further explain sorting. The more I think about it, the insertion sort I went over in class is a little more complex to program than I would like. In fact, a few of my TAs had commented that I should have taught you a simpler sorting algorithm, and on further thought, they are right. I thought the Insertion sort would be good because everyone (practically) has sorted a deck of cards. But when you try to sort this way, it seems for most people, keeping track of everything is a little too much. So, let's try another sort, a Selection sort. After moving the 16 grades to a space in your program that was allocated perhaps by a .BLKW #16 pseudo-op, you are ready to sort these 16 values in place. Let's reduce the number from 16 to 6 just to save time going over it. Suppose your program included: SPACE .BLKW #6. And suppose SPACE is location x3050. And suppose you have moved the six grades. You have: x3050: 81 x3051: 85 x3052: 26 x3053: 99 x3054: 02 x3055: 06 The selection sort works as follows: The first iteration will swap the value in x3050 with the largest value. Then we will have the highest grade in the right place, and the problem is to sort 5 grades. The second iteration will swap the value now in x3051 with the highest of the 5 remaining grades. Then we will have the top two grades in the right place, and the problem is to sort 4 grades. So, we will need to make six iterations in all. Each iteration is needed to fill one slot in the final sorted sequence. (Yes, we can tweak this and optimize, but let's not worry about that in favor of understanding the basic algorithm.) How do we fill the "top" slot in the iteration we are working on. Simple method. Start with two pointers, one keeping track of the slot to be filled, the other sequencing through the rest, looking for the highest grade. We will also need a register to contain the highest grade "so far" and another register to say where that grade is stored. So, for example, in the first pass, we start with R1 pointing to x3050, R2 pointing to x3051. R3 contains 81 - the highest grade so far (we have only looked at one grade so far!) and R4 contains x3050, the address of the location containing the highest grade so far. We will use R5 to contain the value pointed to by R2, as R2 goes through all the locations yet to be examined. I compare R3 (the highest value so far) with R5 (85 - the value pointed to by R2). Since 85 > 81, I put 85 into R3 (85 is the new highest grade so far) and x3051 into R4 (x3051 is the location of the highest grade so far). Then we increment R2. Next, we compare 85 with 26. Since 26 is smaller, we move on. Next, we compare 85 with 99. 99 is bigger so we put 99 into R3 and x3053 into R4. Next 99 with 02. Next 99 with 06. Look at what we have done. Each "next" value is obtained by incrementing R2, and comparing what is there with what is in R3. If we ever move that value to R3, we need to store the address that is in R2 into R4, since R4 keeps track of the address of the highest grade so far. We keep incrementing R2 until we get to the end of memory locations containing grades. Once we reach the end of the grades, we have the highest grade in R3 and its address in R4. That is R3 contains M[R4]. So we swap M[R1] and M[R4], and we are done with that iteration. We go on to the next iteration by moving R1 to point to the next item and continue as above. A snapshot of memory after each iteration yields: x3050: 81 99 99 99 99 99 99 x3051: 85 85 85 85 85 85 85 x3052: 26 26 26 81 81 81 81 x3053: 99 81 81 26 26 26 26 x3054: 02 02 02 02 02 06 06 x3055: 06 06 06 06 06 02 02 You note that the last iteration produced nothing useful since when you swapped the grade that belonged in the next to last slot, you also put the lowest grade in the last slot. So, you can actually do this in n-1 iterations to sort n values. Hope this helps. Good luck finishing the program. Yale Patt