## Bubble Sort for Array

High Level Assembler(HLASM) for MVS & VM & VSE

### Bubble Sort for Array

Hi there I'm pretty new to Assmbler and I was wondering if anybody had some code laying around for a Bubble sort in ASM. I'm learning right now and would just like to see how everything works with the branches and comparisons!
FrankDCC

Posts: 5
Joined: Tue Mar 21, 2017 7:28 pm
Has thanked: 2 times
Been thanked: 0 time

### Re: Bubble Sort for Array

If you are learning HLASM, wouldn't it make more sense for you to WRITE a bubble sort (or quick sort) to learn from?
Robert Sample
Global moderator

Posts: 3720
Joined: Sat Dec 19, 2009 8:32 pm
Location: Dubuque, Iowa, USA
Has thanked: 1 time
Been thanked: 279 times

### Re: Bubble Sort for Array

I'm going to write one, I just want an example in case I get stuck. Plus I want to be able to compare my algorithm to someone who already knows how to write a bubble sort, this way I can gauge how mine is and where to improve on. I know three different high level languages and I have found this is the best way for me to learn and gauge my performance
FrankDCC

Posts: 5
Joined: Tue Mar 21, 2017 7:28 pm
Has thanked: 2 times
Been thanked: 0 time

### Re: Bubble Sort for Array

This is about as minimal as you can get. The bad news is it uses the BXH and BXLE instructions, something beginners absolutely loathe. Registers 2, 3 and 5 are storage addresses. rather than index values, though it would be trivial to set registers 2 and 5 to 0 and 16 and do L 0,NUMBERS(2)/L 1,NUMBERS(3)
BUBBLE   CSECT
USING *,12
SAVE  (14,12)
LR    12,15
LA    2,NUMBERS
LA    4,L'NUMBERS
LA    5,LASTNUM
SORT0100 LR    3,2
SORT0200 BXH   3,4,SORT0500
SORT0300 L     0,0(,2)
L     1,0(,3)
CR    0,1
BL    SORT0400
ST    0,0(,3)
ST    1,0(,2)
SORT0400 BXLE  3,4,SORT0300
BXLE  2,4,SORT0100
DC    H'
0'
SORT0500 RETURN (14,12),RC=0
NUMBERS  DC    F'
10,5,-5,30,20'
LASTNUM  EQU   *-L'
NUMBERS
END   BUBBLE

A very minor performance improvement can be made by changing BL SORT0400 to BNH SORT0400. The second BXLE always branches. Why?

These users thanked the author steve-myers for the post:
FrankDCC (Tue Apr 11, 2017 2:27 am)
steve-myers
Global moderator

Posts: 2105
Joined: Thu Jun 03, 2010 6:21 pm
Has thanked: 4 times
Been thanked: 243 times

### Re: Bubble Sort for Array

cheers
enrico
When I tell somebody to RTFM or STFW I usually have the page open in another tab/window of my browser,
so that I am sure that the information requested can be reached with a very small effort
enrico-sorichetti
Global moderator

Posts: 2996
Joined: Fri Apr 18, 2008 11:25 pm
Has thanked: 0 time
Been thanked: 164 times

### Re: Bubble Sort for Array

Here's my current code, how can I improve it?
TITLE 'SCORE ARRAY SCALER'
EX2    CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
STM   R14,R12,12(R13) SAVE REGISTERS
USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
L     7,LIMIT
LA    6,10
LOOP2    LA    1,0
LA    4,4
LOOP     L     2,ARRAY(1)
L     3,ARRAY(4)
CR    2,3
BNH   SKIP
ST    2,ARRAY(4)
ST    3,ARRAY(1)
SKIP     A     1,FOUR
A     4,FOUR
C     4,LIMIT
BL    LOOP
S     7,FOUR
BCT   6,LOOP2
* STANDARD EXIT:
DONE     L     R13,SAVE+4   RESTORE R13
LM    R14,R12,12(R13)  RESTORE REGISTERS
BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'3'
DC    F'12'
DC    F'9'
DC    F'23'
DC    F'99'
FOUR     DC    F'4'
LIMIT    DC    F'40'
SAVE     DS    18F
END   EX2

I apologize for the format!
FrankDCC

Posts: 5
Joined: Tue Mar 21, 2017 7:28 pm
Has thanked: 2 times
Been thanked: 0 time

### Re: Bubble Sort for Array

1. You've got 5 values, which requires 20 bytes. You have LIMIT set to 40 -- so you're not sorting what you think you're sorting.
2. Using register 1 is not a good idea -- registers 0, 1, 13, 14, 15 all have special purposes in HLASM and hence should NOT be used except for their special purpose.
3. Try changing the order of your values to ensure they are sorting correctly.
4. There's usually more than one way to do things in HLASM -- LA R4,4(R4) requires less memory access than A R4,FOUR.
5. As a result of #1, your value of FOUR does not remain 4 -- which has an impact on how register 7 changes value.

These users thanked the author Robert Sample for the post:
FrankDCC (Tue Apr 11, 2017 2:27 am)
Robert Sample
Global moderator

Posts: 3720
Joined: Sat Dec 19, 2009 8:32 pm
Location: Dubuque, Iowa, USA
Has thanked: 1 time
Been thanked: 279 times

### Re: Bubble Sort for Array

Would it be possible to give me a code revision to see what I did wrong?
FrankDCC

Posts: 5
Joined: Tue Mar 21, 2017 7:28 pm
Has thanked: 2 times
Been thanked: 0 time

### Re: Bubble Sort for Array

This will not work. I mainly doctored it to correct some of the issues Mr. Sample noted, particularly point 1. It does assemble cleanly. My little sample a couple of posts back uses a slightly different method to establish the array limits.

Mr. Sample's concern about the use of register 1 is something you should remember, but is not significant in your code. Any time you use an IBM macro you must assume registers 0, 1, 14 and 15 are going to be trashed. Most of my code uses these registers as short term work registers quite heavily. In most of my programs register 1 or register 15 is the most frequently referenced register. In a program I've been working on these last 2 weeks, a little over 1000 lines, register 1 has 158 references and register 15 has 206 references. The next most used register has 91 references.

Anyway, here is your doctored program -

TITLE 'SCORE ARRAY SCALER'
EX2      CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
STM   R14,R12,12(R13) SAVE REGISTERS
USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
L     7,LIMIT
LA    6,COUNT
LOOP2    LA    1,0
LA    4,L'ARRAY
LOOP     L     2,ARRAY(1)
L     3,ARRAY(4)
CR    2,3
BNH   SKIP
ST    2,ARRAY(4)
ST    3,ARRAY(1)
SKIP     A     1,FOUR
A     4,FOUR
C     4,LIMIT
BL    LOOP
S     7,FOUR
BCT   6,LOOP2
* STANDARD EXIT:
DONE     L     R13,SAVE+4   RESTORE R13
LM    R14,R12,12(R13)  RESTORE REGISTERS
BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'
3'
DC    F'
12'
DC    F'
9'
DC    F'
23'
DC    F'
99'
COUNT    EQU   (*-ARRAY)/L'
ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'
ARRAY*COUNT)
SAVE     DS    18F
END   EX2

COUNT EQU (*-ARRAY)/L'ARRAY

*-ARRAY computes the number of bytes between the current value of the location counter and the value assigned to ARRAY; L'ARRAY directs the Assembler to use the length attribute of ARRAY. So COUNT is the number of words in ARRAY. Add another word, and the Assembler updates COUNT automatically. You see essentially the same thing in C from time to time:

int array[] = {3, 12, 9, 23, 99};
int count = sizeof(array) / sizeof(array[0]);

Mr. Sample's point 4 talks about replacing A 4,FOUR with LA 4,4(,0,4) to eliminate a storage reference. Storage, relative to computer instruction processing rate is s-l-o-w. In the 1990s, IBM added the first of the immediate instructions because they finally realized storage is s-l-o-w, though LA has been used for this purpose by Assembler guys for more than 40 years in spite of serious problems that have caught programmers by surprise more than once. Today we might use AHI 4,4 rather than LA. In the last 10 years IBM has added immediate instructions with 32 bit operands though most of us use them infrequently, if at all.
steve-myers
Global moderator

Posts: 2105
Joined: Thu Jun 03, 2010 6:21 pm
Has thanked: 4 times
Been thanked: 243 times

### Re: Bubble Sort for Array

steve-myers wrote:This will not work. I mainly doctored it to correct some of the issues Mr. Sample noted, particularly point 1. It does assemble cleanly. My little sample a couple of posts back uses a slightly different method to establish the array limits.

Mr. Sample's concern about the use of register 1 is something you should remember, but is not significant in your code. Any time you use an IBM macro you must assume registers 0, 1, 14 and 15 are going to be trashed. Most of my code uses these registers as short term work registers quite heavily. In most of my programs register 1 or register 15 is the most frequently referenced register. In a program I've been working on these last 2 weeks, a little over 1000 lines, register 1 has 158 references and register 15 has 206 references. The next most used register has 91 references.

Anyway, here is your doctored program -

TITLE 'SCORE ARRAY SCALER'
EX2      CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
STM   R14,R12,12(R13) SAVE REGISTERS
USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
L     7,LIMIT
LA    6,COUNT
LOOP2    LA    1,0
LA    4,L'ARRAY
LOOP     L     2,ARRAY(1)
L     3,ARRAY(4)
CR    2,3
BNH   SKIP
ST    2,ARRAY(4)
ST    3,ARRAY(1)
SKIP     A     1,FOUR
A     4,FOUR
C     4,LIMIT
BL    LOOP
S     7,FOUR
BCT   6,LOOP2
* STANDARD EXIT:
DONE     L     R13,SAVE+4   RESTORE R13
LM    R14,R12,12(R13)  RESTORE REGISTERS
BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'
3'
DC    F'
12'
DC    F'
9'
DC    F'
23'
DC    F'
99'
COUNT    EQU   (*-ARRAY)/L'
ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'
ARRAY*COUNT)
SAVE     DS    18F
END   EX2

COUNT EQU (*-ARRAY)/L'ARRAY

*-ARRAY computes the number of bytes between the current value of the location counter and the value assigned to ARRAY; L'ARRAY directs the Assembler to use the length attribute of ARRAY. So COUNT is the number of words in ARRAY. Add another word, and the Assembler updates COUNT automatically. You see essentially the same thing in C from time to time:

int array[] = {3, 12, 9, 23, 99};
int count = sizeof(array) / sizeof(array[0]);

Mr. Sample's point 4 talks about replacing A 4,FOUR with LA 4,4(,0,4) to eliminate a storage reference. Storage, relative to computer instruction processing rate is s-l-o-w. In the 1990s, IBM added the first of the immediate instructions because they finally realized storage is s-l-o-w, though LA has been used for this purpose by Assembler guys for more than 40 years in spite of serious problems that have caught programmers by surprise more than once. Today we might use AHI 4,4 rather than LA. In the last 10 years IBM has added immediate instructions with 32 bit operands though most of us use them infrequently, if at all.

Thank you very much for the helpful information and the updated code, first and foremost! The reason I have not been using the mentioned:
COUNT    EQU   (*-ARRAY)/L'ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'ARRAY*COUNT)

is because I have not been taught how to do so yet, the only way I know how so far is the way I posted originally and I don't think I'm at liberty to skip ahead even if it's a better way. I do understand the point of using LA vs A though to eliminate a storage reference and will do so! Is there anyway you can "doctor" my code a bit more with the restrictive knowledge that I have / can use?
FrankDCC

Posts: 5
Joined: Tue Mar 21, 2017 7:28 pm
Has thanked: 2 times
Been thanked: 0 time

Next