Sort and Search. Geek alert, there's programming stuff here. Sorry.

I was (am??) an IBM mainframe assembler programmer for 50 years. And liked it.
However, I gotta admit, html is light years easier and faster.
In the early '70s, my boss was looking for a character string, maybe his name, in a file.
He wrote a COBOL program to read a file, and search for the character string.
But the search he coded was SLOW, so I told him I could do it better, and faster, and I did.

What you do initially, is find the least frequently used character in the string.
Then you scan each record, looking for that character. After finding it, then you do the compare.
IBM has an instruction that allows you to look for any of several different characters, in a record, all at the same time.
So you can search for multiple strings, all at the same time. (It is pretty cool.)

A few years later, The Bank, leased FILEAID, which wasn't faster, but was much better.
Many years after that, IBM included that function in ISPF (kind of like html from your desk).
I like that idea of finding strings, and have coded a couple programs that are somewhat similar, with variations.
But I never finished the last one, that would have included all of the various functions.

Sort is another interesting process. Maybe first, we should divide sort into 2 major categories.

• Sorting records, from one file to another. That's what typical sort programs do.
• Sorting records that are in a table, in mrmory. There are many different algorithms to do this.

Sort in an existing table is what I'm doing. For several years, I worked 3 days a week, 12 hours a day.
(Yeah, tough life.) But that job provided me with lots of free time, and I coded many common routines.
One of those was sorting a table. There are many different sort algorithms, but I just used an easy one.
2-3 months ago, I thought I'd try to write one that's more efficient - essentially does fewer compares and swaps.
I wrote a program that compares 3 different algorithms:

• Bubble sort - easiest, go through the list and swap records that are out of order.
  Do that repeatedly, with a shorter list each time, until your done.
  
• Select sort - similar, go through the list and find the lowest record.
  Swap it with the first (or last) record, then do it again, with a shorter list, until you're done.
  
• Quiksort - by far the most complicated, but the fastest.
  1. Pick a record that you hope is the middle record.
  2. Start from one end and find a record that's lower.
  3. Start from the other end and find a record that's higher.
  4. Swap those 2 records.
  5. Continue that process until you get to the middle.
  6. At that point, you have 2 lists, one with low records and one with high records.
  7. Save the longer list, and work the shorter list, repeatedly, until the list is 1 entry.
  8. Go pick up the last saved pair of addresses, and repeat this process.
  9. When there are no more saved lists, you're done.
  As I said, QuikSort is more complicated, but you're working with shorter lists, so it's faster.

  There are a couple more things. You can write MACROs, which allow you to use that code, and substite
  things (addresses) into it as it's run. I like writing them, but they are more complicated.
  
  There are also various kinds of programs that have different requirements:

  • 'Regular' programs just run, and go away. There are no restrictions on them.
  • Reuseable programs can be reused in memory, without reloading them.
  • Re-entrant programs can be used many times simultaneously.
  • Re-locatable programs can be used simultaneously, but, between uses, can be moved to somewhere else in memory.

  I started to write Quiksort as a re-entrant macro, and couldn't get it to work.
  So I'm in the middle of writing it, not as a MACRO, but as re-entrant.
  Why? Just because. Sometimes there is no rhyme or reason.
  I believe that there's some dementia starting, and I thought it'd be good exercise.
  But, of course, I have to test it, so I wrote a program that loads table, and then does all 3 types of sort,
  and reports elapsed time for each. (It took me 3 days, just to get the timer routine working correctly.)
  The time from IBM is accurate, but the numbers are not easy to work with.
  
  In any case, html is so easy, and you can see what you're doing immediately, and mistakes are obvious
  and easily fixable, that I'm having a hard time finishing my Quiksort.
  Maybe worse, I doubt that anyone will ever use my Quiksort.
  Of course, noone will ever look at my website either, so there's that.
  
  Eventually, if Quiksort ever works, I'll post the timings of the 3 sort routines. Don't hold your breath.
  

  Just for giggles, I just wrote, and tested, the code for a bubble sort.
  (After a couple tries, it works.) There are half a dozen instructions that load registers,
  and some print-report instructions, but this is the actual sort code, only 10 instructions.
  This same code sorts the table, both ascending and descending.
  The code for select sort would be similar, but the 3 MVC (move character)
  instructions would only be done after the end of the first loop. That would run faster.
  
  In classical assembler, which this is, cols 1-8 contain the label if there is one.
  Cols 10-14 (sometimes longer) contain the op-code (operation code).
  Cols 16 on contain the field(s), sometimes one, sometimes 2, very rarely (BXLE) 3.
  
  BUBBNOP  NOP   BUBBBXLE
  BUBBCLC  CLC   0(3,R2),20(R2)      Q. RECORDS IN ORDER?
           EX    R5,BUBBNOP          YES, LEAVE 'EM ALONE.
           MVC   12(20,R13),0(R2)    NO, MOVE FIRST TO S/A
           MVC   0(20,R2),20(R2)         MOVE 2ND TO 1ST SLOT
           MVC   20(20,R2),12(R13)       MOVE 1ST TO 2ND SLOT.
  BUBBBXLE BXLE  R2,R14,BUBBCLC          BUMP INDEX AND LOOP
           SR    R15,R14             BACK UP THE ENDING LOC
           LR    R2,R3               RESTART AT TOP OF TABLE
           BXLE  R2,R14,BUBBCLC      AND LOOP.
  
  Next is the code for select sort.  In both cases, the main loop goes from CLC to the first BXLE.
  In the bubble sort, that's 6 instructions, including 3 MVC, which can be a bit slow.
  In the select sort, the loop is only 4 instructions, and doesn't include the MVC instructions.
  That makes it faster. If it's 5-10-20 records, who cares. If it's 2,000 records, then it counts.
  
  SEL4     LR    R2,R3               POINT TO FIRST REC
           LR    R1,R3
           B     SELBXLE
  *
  SELNOP   NOP   SELBXLE
  SELCLC   CLC   0(3,R2),0(R1)    Q. DO WE HAVE THE LOW REC ADDR?
           EX    R5,SELNOP           YES, TRY THE NEXT.
           LR    R1,R2               NO, SAVE THE NEW LOW.
  SELBXLE  BXLE  R2,R14,SELCLC       BUMP INDEX TO NEXT REC, AND LOOP
           CR    R1,R3            Q. DO WE NEED TO SWAP?
           BE    *+22                NO, BRANCH AROUND THE SWAP
           MVC   12(20,R13),0(R1)      MOVE FIRST TO S/A
           MVC   0(20,R1),00(R3)       MOVE 2ND TO 1ST SLOT
           MVC   00(20,R3),12(R13)     MOVE 1ST TO 2ND SLOT.
           BXLE  R3,R14,SEL4         AND LOOP.
  
  The select sort is what I used in my coding at work.
  Faster than bubble, and far easier to understand than Quiksort.
        

  And now for something completely different, a program to read a file, and copy records
  that contain a specified character string. I talked about this at the top, then wandered off
  into the weeds of sort. In general, table sort is a subroutine. Selecting and copying
  records that contain a specific character string is a stand-alone program.
  I wrote 3 programs, of increasing complexity.
  

  • Straight, simple, copy program. Open the files, read and write records. About 30 lines of code.
  • A simple search program, that has no frills, but does find, and copy records. About 60 lines.
  • A reasonably well written search, that shows file stats, and performance stats. 500 lines.
    All 3 are in a simgle file, with some description.
    
  3 programs.
  
  

  Old programmers, like me, pretty much can't help themselves from being concerned about speed.
  I wrote a program in the '70s, that ran, on IBM's fastest, in 21 minutes.
  About 15 years later, that same program ran in 71 seconds, on IBM's top of the line business machine.
  There are times when efficiency does matter, but not nearly as often as before.
  
  You'll notice that, in the 2 smaller programs, I've gone back and added some documentation.
  That's not done in the longer program. The problem that exists is that my fingers cannot keep
  up with my thinking, and if I take time to write notes, I'll lose my train of thought.
  Sometimes I go back later and add comments, sometimes not. Depends on what else I'm doing at the moment.