!pr2
Sorting and Swapping.......................Bob Sander-Cederlof

Jack McDonald, writing in the July 1984 Software News, posed a puzzle for programmers:  using nothing more than a series of calls to a SWAP, sort five items into ascending order.  SWAP compares two items according to the indexes supplied, and exchanges the items if they are out of order.  For example, calls on SWAP which follow the pattern of a "Bubble Sort" would look like this:

    SWAP (1,2)    SWAP (1,2)    SWAP (1,2)    SWAP (1,2)
    SWAP (2,3)    SWAP (2,3)    SWAP (2,3)
    SWAP (3,4)    SWAP (3,4)
    SWAP (4,5)

That is ten swaps, which is more than necessary.  You can do it in nine, which was McDonalds Puzzle.  He gave an answer, and I found another.  It was fun writing some quick code to test various swap-lists.

First I wrote a macro named "S" which loaded the two index numbers into X and Y, and called a subroutine named SWAP.  See it in lines 1030-1070.

Then I coded SWAP (lines 1200-1290), which compared two bytes at BASE,X and BASE,Y; if they were out of order, I swapped them around.  To make things easy for me, I put BASE at $500, which just happens to be the third line on the video screen.  That way I could watch everything happen without struggling to code I/O routines.

I wrote a program which would initialize a 5-byte string to all $01 (no program, really just a data definition at line 1670); another which copies the string to BASE (LOAD, lines 1590-1650); another which counts up from 0101010101 to 0505050505, so that all possible combinations would be run through (NEXT, lines 1770-1870); and another to do all these in connection with SORT, which performed a list of SWAP calls.  The result was a method for visualizing and checking various groups of SWAPs to see if they could sort any initial permutation into ascending order.  Assemble, and type MGO NEXT to see it all work.

Here is the code, with two possible SWAP orders which work, of nine steps each.
!np
I also got interested in permutation generation, and came up with the following macros and code to generate all 120 permutations of five items, without any extra steps, each step being the simple interchange of two items.  Assemble, and type MGO PERMUTE to see it generate 120 strings of the letters ABCDE in different arrangements.
