% Author Evgeny Eremin % Program for section 5.2.2 % 2002-07-08 12:23 % algorithm from 5.2.2 from "TAOCP" (algorithm B - bubble sort) % The task. % N elements, which are stored in INPUT, INPUT+2, ..., INPUT+2*(N-1) % memory addresses must be sorted by means of bubble method. % Address INPUT is supposed to be already defined in $0. % The solution. % N - number of sorting elements Nb IS 2 % number of bytes for sorting data (2-byte integer) INPUT IS $0 % the initial absolute data address (already set!) BOUND IS $1 % the address of the last element to sort j IS $2 % current address t IS $3 % t = j - INPUT Kj IS $4 % Kj Kj1 IS $5 % Kj+1 tmp IS $6 % temporary data: results of compare 01 START SETL t, Nb*(N-1) % 1 B1. Initialize BOUND (set t % to the last element) 02 1H ADD BOUND, INPUT, t % A BOUND <== INPUT + t (its address) 03 ADD j, INPUT, 0 % A B2. Cycle for j.j <== INPUT 04 SETL t, 0 % A t <== 0 05 3H LDW Kj, j, 0 % A B3. Compare andswap elements 06 3MH LDW Kj1, j, Nb % C extract both into registers 07 CMP tmp, Kj, Kj1 % C no swap 08 BNP tmp, 5F % C if Kj<=Kj1 09 STW Kj1, j, 0 % B save Rj1 10 STW Kj, j, Nb % B save Rj 11 SUB t, j, INPUT % B t <== j - INPUT 12 JMP 2F % B skip: last element is already in Kj 13 5H ADD Kj, Kj1, 0 % C-B move last element to Kj register 14 2H INCL j, Nb % C j <== j + Nb 15 CMP tmp, j, BOUND % C repeat cycle 16 BNB tmp, 3MB % C if J < BOUND 17 4H BPB t, 1B % A B4. Any swap? If t > 0 then step B2