Page 90 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes 6.2 Interchange Sort

Here we will recognize how to sort a table by means of interchange sort. There are a many ways
of performing this, some simple and some complex. Figure 6.1 is a segment of coding that
executes an interchange sort.

Did u know? Interchange sort is also known as a bubble sort, a sinking sort or a sifting
sort.

This simple sort considers contiguous pairs of items in the table and places them in order
(interchanges them) as necessary. Such a sorting algorithm is not very competent, but it is easy.

Figure 6.1: Example of Interchange Sort in 360 Assembly Code

L 5,LAST
LA 4,SYMTBL
LOOP CLC 0(8,4),14(4) Compare adjacent symbols – 8 bytes
BNH OK Correct order
MVC TEMP(14),0(4) Switch entries
MVC 0(14,4),14(4) · · ·
MVC 14(14,4),TEMP · ·
OK A 4,=F’14’ Move to next entry
C 4,LAST Is it last entry
BNE LOOP No

SYMTBL DS 0F Symbol table
DS 100CL14 14 bytes per entry
TEMP DS CL14 Temporary entry
LAST DC A(-----) Location of next free entry in table

Example: Now we show an example to see how it works. Consider the table of 12
numbers displayed in Figure 6.2.

Figure 6.2: Illustration of Interchange Sort

Unsorted 1st 2nd 3rd 4th 5th 6th 74th and
List pass final pass
19 13 05 05 01 01 01 01
Order of 13 05 13 01 05 05 05 02
comparison 05 19 01 13 13 13 02 05
27 01 19 19 16 02 09 09
01 26 26 16 02 09 11 11
26 27 16 02 09 11 13 13
31 16 02 09 11 16 16 16
16 02 09 11 19 19 19 19
02 09 11 21 21 21 21 21
09 11 21 26 26 26 26 26
11 21 27 27 27 27 27 27
21 31 31 31 31 31 31 31

84 LOVELY PROFESSIONAL UNIVERSITY