Page 1 of 1

Selection Sort

PostPosted: Sat Nov 22, 2014 9:57 pm
by Susansuth
I have a program I'm working on where we build a table with 27 byte entries where we compress a lot of data about students (by converting it into binary and moving the bits closely together). We also have a subroutine to run a bubble sort and a subroutine to run a selection sort. After each routine, we decompress the data and print it. So, at the end, we get a list of basic unsorted data, one where it's sorted by major and one where it's sorted by GPA.

There is an odd problem with the sorting by major routine (selection sort) which I've noticed happens in both my routine and in the output the professor gave us for our homework. Basically, we have compressed binary data for 18 bytes, then we have an uncompressed major for four bytes, a packed decimal for the GPA, and then 3 bytes of compressed binary data.

When I run the selection sort, it works, after a fashion. But what it does is to have the first 18 bytes correct. Then, it splits up the data and pulls it in from another line in the table.

So, if I have the following data in the original table: Q12345678 password 22112014 CHEM 400 20 04, after sorting, it might change it to Q12345678 password 22112014 SOCI 350 18 03.

Why would it do this?

I keep thinking that the fact that the major is uncompressed data is screwing with the sorting somehow.

Can you take a look at my code and see if there's something more obvious to you than it is to me?
 SORTMAJ  CSECT                                                         
          STM   14,12,12(13)            SAVE REGISTER CONTENTS         
          BALR  12,0                    ESTABLISH BASE REGISTER         
          USING BASEPT3,12                                             
 BASEPT3  DS    0H                                                     
          LM    2,3,0(1)                LOAD PARAMETERS INTO REGS       
 *                                                                     
 BEGIN    LA    4,0(2)                  LOADS TABLE PTR INTO R4         
          LA    5,27(2)                 LOADS INDEX PTR INTO R5         
 *                                                                     
 SMLOOP   CLC   18(4,4),18(5)           COMPARES THE TWO MAJORS     
          BC    B'1100',SKIP1           BRANCHES TO SKIP1 IF NOT HIGHER
          C     5,0(3)                  COMPARES R5 TO END OF TABLE     
          BC    B'1000',SKIP1           BRANCHES TO SKIP1 IF EQUAL     
          LA    4,0(5)                  LOADS ADD OF R5 INTO R4         
 *                                                                     
 SKIP1    LA    5,27(5)                 LOADS ADD OF NEXT TBL VAL IN R5
          C     5,0(3)                  COMPARES R5 TO END OF TBL (R3)   
          BC    B'0101',SMLOOP          BRANCHES TO SMLOOP IF LOWER THAN
          CLC   0(27,4),0(2)            COMPARES R2 to R4                               
          BC    B'1000',SMLOOP          IF EQUAL, BRANCHES TO SMLOOP                                 
 *                                                                       
          XC    0(27,4),0(2)            DOES THE SWAP                             
          XC    0(27,2),0(4)                                             
          XC    0(27,4),0(2)                                             
 *                                                                       
          LA    2,27(2)                 MOVES TO NEXT SLOT IN TABLE     
          C     2,0(3)                  COMPARES R2 WITH END OF TABLE   
          BC    B'0101',BEGIN           IF LOWER THAN, BRANCHES TO BEGIN
 *                                                                       
          LM    14,12,12(13)            LOADS REGISTERS BACK             
          BR    14                      EXIT TO MAIN ROUTINE             
          LTORG


I'd appreciate the help! Thank you!

Susan

Re: Selection Sort

PostPosted: Sun Nov 23, 2014 3:58 am
by steve-myers
Something like this can go wrong in many different ways; there is just not enough stuff here to even start an analysis.

Your idea of specifying a condition mask in the BC instructions is good. It's certainly better than 8 or 12. This might surprise you, but after 45+ years writing /360 Assembler I don't have the bit meanings in B'0xx0' masks in BC instructions memorized! I think the only time I've ever used B'xxxx' masks in a BC instruction was after AL/SL instructions used for 64 bit arithmetic.

I'm sort of dubious about C 5,0(3) for the purpose stated in the comment. Is the address of the end of the table in register 3, or does register 3 point to a word is storage that has the address of the end of the table? I can see register 3 came from the parameter list, so I'd be more inclined to believe the first idea, in which case CR 5,3 might be more appropriate. Same thing with C 2,0(3) later in the code.

Your mask B'0101' looks a bit suspect. B'xxx1' is usually "overflow" after a compare or math operation. Which reminds me of a war story. About the beginning of the year I put up an example of code to compute elapsed time from SMF data on our sister site. This is more complicated than it sounds, as there are two potentially discontinuous times in SMF data: time of day recycles from 8640000 to 0, and day of year, which recycles from 365 or 366 to 1 (but not 0). The output from the program is in time of day units, 1/100th second. I knew going in there was a potential for overflow since the time would overflow after 248+ days. The program tested for overflow after every math operation and would abort on overflow. OK so far. After I put the program up, I realized there was a conceptual problem. Most of the time the program mask bit setting for fixed point overflow interrupts is set to 0. Since I'm testing for overflow myself, I do not want to take a program interrupt for an overflow, so I changed my copy of the program to save and restore the program mask, and then turn off the program mask bit for fixed point overflow interrupts.

Now I have a program that actually does this math, and I had noticed a problem that I hadn't resolved. It was adding these elapsed times, and it was sometimes getting funny results. I finally realized my funny results were really an overflow issue. Not from the SMF data itself, which was fine, but from adding these elapsed times. Understanding a problem usually means it is not too terribly difficult to fix the problem.

One more comment. Something like 0(3) in an RX instruction is fine. It will do the address arithmetic you expect. But, in the low end System/360 machines, 0(3,0) was actually slower than the more correct 0(0,3)! These machines were so slow anything to speed things up was acceptable! To this day I don't like seeing something like 0(3). I want to see 0(0,3), though I will accept (and usually write) 0(,3). Of course, this will cross me up, too. Lot's of times I'll write L x,0(0,x) and then change it to an ICM to get the condition code, and I'll write ICM x,B'1111',0(,x). Oops. The Assembler won't take that!

Re: Selection Sort

PostPosted: Sun Nov 23, 2014 4:17 am
by Susansuth
Thank you for the reply! I appreciate it!

I wasn't sure whether I should load up more than just that routine or not. I can put the other routines here if you think it would be helpful. I just didn't want to bog anyone down with a bunch of my code. LOL!

I have a lot of trouble determining which is the correct thing to use with the compare type statements. Register 3 does point to a word in storage that has the address of the end of the table. So CR 5,3 and CR 2,3 might be better?

I didn't think about the RX instruction issue. I'll try to remember to change that for the future! That makes a lot of sense!

Thank you for your help. If you'd like to see the other code, let me know and I will load it here.

Susan

Re: Selection Sort

PostPosted: Sun Nov 23, 2014 8:33 am
by Susansuth
Thank you again for your help. I really appreciate it.

I've got the program working now. Apparently, whatever I did to fix the program ironed out the problem where it was switching pieces of the data, too.

I'm not sure HOW I did it, but I was very excited that after a week of work on it that it DID work. :D

Thanks for all your help and advice. It has been a Godsend. :)

Susan

Re: Selection Sort

PostPosted: Sun Nov 23, 2014 9:26 am
by steve-myers
Susansuth wrote:... Register 3 does point to a word in storage that has the address of the end of the table. So CR 5,3 and CR 2,3 might be better? ...

Then the code you posted should be correct.
Susansuth wrote:... I have a lot of trouble determining which is the correct thing to use with the compare type statements. ...

This is something you have to clarify and understand in your own mind. After 45+ years, I still have trouble, sometimes, deciding which mask to use in BC instructions.
Susansuth wrote:... I didn't think about the RX instruction issue. I'll try to remember to change that for the future! That makes a lot of sense! ...

Actually, it doesn't seem to make much sense. In some ways we were closer to the hardware in the 1960s than people are these days. d(x,b) (the RX instruction address specification) implies a three input adder in the hardware. The instruction decode logic in the high end System/360 machines - by "high end" I mean the models 65 and up - had a dedicated three input adder for this purpose so it didn't matter. In the low end machines this was not true. d(x,b) went through the same two input adder as was used for regular arithmetic. First it did d(b), then, if x was non-zero, it added the contents of x to the result of d(b). That's why 0(3,0) is slower than 0(0,3) or 0(,3).