CS-220, Sec. 90, Week 9-A
R. Eckert

SELECTION SORT USING INDEXING

One important use of assembly language indexing is in sorting. Here we
are usually after good performance (fast execution), so it makes sense to
use assembly language. The following illustrates how 80x86 indirect
addressing can be used to implement a simple sorting algorithm--the
selection sort.

Assume we want to sort a list of N numbers in descending order (greatest
to least). The selection sort takes the first value in the list and
compares it with all of the others. Any time it finds that next number is
greater than the first value, it swaps the two. After that pass through
the data is done, the first position in the list will contain the largest
number. The algorithm then does the same thing with the second number in
the list. It is compared with all the other numbers, and any time the
next number is greater, a swap is made. After this second pass, the
second position will contain the second greatest number. The procedure is
repeated for a total of N-1 passes through the data. After the last pass,
the list will be ordered.

As an example, assume we have a list of 4 numbers: 23, 17, 86, 42, that
are to be sorted into descending order. We will keep track of the "pass
number" and the "next position" on any given pass.

                                           List of Data--
 Pass #   Next pos'n  Numbers compared     position:  0   1   2   3
 --------------------------------------------------------------------
                                                      23  17  86  42
   0          1       23 with 17 ==> no swap          23  17  86  42
   0          2       23 with 86 ==> swap             86  17  23  42
   0          3       86 with 42 ==> no swap          86  17  23  42
   -----------------------------------------------------------------
   1          2       17 with 23 ==> swap             86  23  17  42
   1          3       23 with 42 ==> swap             86  42  17  23
   -----------------------------------------------------------------
   2          3       17 with 23 ==> swap             86  42  23  17
   -----------------------------------------------------------------

Let's now make a flow chart that could be used to develop assembly
language code to implement the selection sort algorithm. We'll assume
that TABLE is the name of the list, and we'll use DI to point to the
offset (relative to the start of the table) of the "pass number" and BX
to point to the offset of the "next position".

                DI <--- 0
                     |
                     |<------------------------------------
                     |                                     |
                BX <-- DI + 1                              |
                     |                                     |
                     |<--------------------------------    |
                     |                                 |   |
           TABLE[BX] > TABLE[DI]?  ----------          |   |
                     |               yes     |         |   |
                     | no                || Swap ||    |   |
                     |                       |         |   |
                     |<----------------------          |   |
                     |                                 |   |
                BX <-- BX + 1                          |   |
                     |                                 |   |
                  BX < N?  ----------------------------    |
                     |              yes                    |
                     | no                                  |
                     |                                     |
                DI <-- Di + 1                              |
                     |                                     |
                  DI < N-1? -------------------------------
                     |              yes
                     | no
                     |
                   Done