sorting integer arrays

Discussions about the BBC BASIC language, with particular reference to BB4W and BBCSDL
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

Thanks, Matt, for another interesting reply. If you check my code again, I think you'll find it covers the whole input. Here's a test program which certainly works correctly.

DIM a%(15)
a%() = 3,6,2,18,7,0,101,19, 20, 12, 45, 7, 66, 29, 15

PROC_showContents
PROC_sort (a%())
PROC_showContents

END

DEF PROC_sort (a%())
flag% = 0
WHILE NOT flag%
flag% = -1
size% = DIM(a%(),1)
FOR i% = 1 TO size% - 1
IF a%(i%) > a%(i% + 1) THEN
SWAP a%(i%), a%(i% + 1)
flag% = 0
ENDIF
NEXT i%
ENDWHILE
ENDPROC

DEF PROC_showContents
size% = DIM(a%(),1)
FOR s% = 1 TO size%
PRINT a%(s%);
NEXT s%
PRINT

I prefer to work with lower case commands, but do to the lack of syntax colouring here I capitalised it to make things easier to read. Some of the other programming language forums have a feature to allow you to post code retaining both indentation and syntax colouring. Is there a way to do that with the BB4W forum? ;)
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

Whoops, the final ENDPROC didn't copy across!
MattC
Posts: 114
Joined: Mon 16 Apr 2018, 06:17

Re: sorting integer arrays

Post by MattC »

ArryMan wrote: Mon 07 Feb 2022, 10:49 If you check my code again...
Sorry, you're right. I wasn't reading it correctly. This program does in deed work. However, at the risk of sounding picky :oops: (it's certainly not my intension to be negative), I played around with it and included a loop counter - in both of ours. The WHILE loop, as a minimum, takes at least the same number as the nested FOR loop. In fact, occasionally, it loops twice the number. It's an interesting concept and one to play with.
ArryMan wrote: Mon 07 Feb 2022, 10:49 I prefer to work with lower case commands
I started using BBC Basic when the BBC Micro first came out. At that time all commands had to be uppercase, so I've grown up using them that way. It seems more natural to me, but I understand, looking at other languages (although I haven't done much work on any other), that lowercase seems to be the norm. In my opinion, that's just one small reason that make BB4W different.
ArryMan wrote: Mon 07 Feb 2022, 10:49 Some of the other programming language forums have a feature to allow you to post code retaining both indentation and syntax colouring. Is there a way to do that with the BB4W forum?
I don't believe so. But you can use the 'Code display'. This displays it as non-proportional coding. Looks slightly better.

Out of interest, how long have you been coding?

Matt
DDRM

Re: sorting integer arrays

Post by DDRM »

Hi Both,

There are some issues here: I'll get back to you on it when I get a chance...

Best wishes,

D
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

Hi, Matt, this is turning out to be an interesting rally! I started coding before even the ZX81 appeared on the scene. I was at Thurrock Technical College doing my HNC, and we coded with a teleprinter and hand-set modem connected remotely to the only computer in Essex at the Chelmer College some 20 miles away! We were doing Basic even then.

Then I got my first computer, a Spectrum 48k. I just loved the keywords right on the rubber keyboard, and the fact that if you coloured a word for the display, the actual code would be coloured. I learnt to use the inbuilt processor, a Zilog Z80, in machine code. Since then I've dabbled in them all. I even did a long thin module in C as a degree module and later C++. Did some AI languages, then Java, Python, etc.

I'm currently doing a music quiz prog for one of my daughters, a music teacher, who wants it for her students. It's just about ready now, so will probably rework it later in Python to get a "Windowy" GUI using TKinter.

Bottom line - program is fun and keeps me young. But I'd love to be back at the keyboard of a Spectrum again!

Dave.
DDRM

Re: sorting integer arrays

Post by DDRM »

Hi Arryman,

Your routine has one serious flaw (which you actually see in your posted example, which "loses" the initial 3 and introduces an extra 0), and one inefficiency you might want to be aware of:

1) The serious flaw is that BBC BASIC arrays are 0-based (that is, there is an element 0): if you assign content with a statement like
a%() = 5,3,7,9,1,12

The 5 gets put in a%(0), which would never get sorted by your routine, which starts with an index of 1.

On the other hand, many people use their arrays starting from position 1 - so if you corrected this flaw, you would find yourself sorting a%(0) (which would be 0) into the intended data. That won't be a problem if all your data are positive (or at least non-negative) numbers, but would be if there are negative numbers in the data, since one of them will get sorted into position 0 (and "lost to follow-up", as the doctors say), while a stray 0 would appear in your data!

You will note that the library sort routine offers the option to handle this by passing it array(1) when you call it. You might want to amend your routine to have a parameter that determines whether it considers the array as 0-based or 1-based (or indeed, if it offers the option to sort only a subset of the array, as the library one does.

2) The inefficiency is that your structure, using a flag to check for any changes, but looping through the whole array each time, can be even more inefficient that a standard bubble sort, because after the n'th pass we know that the top n elements are the largest in the array: we don't need to check them again. While this doesn't change the overall complexity of the routine (it's still O(n^2) - in other words it grows in length by the square of the number of elements), it could take roughly twice as many comparisons (think of it as working down the leading diagonal of the "square", but only doing the top half).

On the other hand, your system using a flag can save a lot of time if the array is already almost sorted, since you stop as soon as there are no more swaps.

I tend to implement bubble sorts "the other way up", i.e. putting the lowest in place first:

Code: Select all

      DIM a%(15)
      a%() = 3,4,5,6,7,10,8,7, 20, 12, 45, 67, 66, 29,42,45

      PROC_showContents
      REM Note correction to remove the space between procedure name and bracket
      REM I think your version only worked because you used the same (global) name for the array inside the procedure
      PROC_sort(a%(),0)
      PROC_showContents

      END

      REM Note my version sorts the LOWEST values first (More intuitive for the nested loops)
      REM Note that passing arrays in and getting them back relies on "pass by reference"
      REM - it wouldn't work to change a "normal" variable (unless you used RETURN)
      DEFPROC_sort(a%(),base%)
      LOCAL x%,y%,size%
      size% = DIM(a%(),1)
      FOR x% = base% TO size%-1
        FOR y%=x%+1 TO size%
          IF a%(x%)>a%(y%) THEN SWAP a%(x%),a%(y%)
        NEXT y%
      NEXT x%
      ENDPROC

      DEF PROC_showContents
      size% = DIM(a%(),1)
      REM Note change to start from a%(0)
      FOR s% = 0 TO size%
        PRINT a%(s%);
      NEXT s%
      PRINT
      ENDPROC
Best wishes,

D
DDRM

Re: sorting integer arrays

Post by DDRM »

As an aside, which version of BBC BASIC are you using? If you are using the BB4W version, I would suggest it will be easier to write a "pretty" Windows interface in BB4W than in Python with TKInter! Have a look at the relevant bits of the manual, and some of the examples. If you are using the SDL version the windowed version might look a bit less "standard windows", though it will probably still be nicer than you'll get in TKInter, but on the upside you could use it on different platforms, including mobile phones!

Best wishes,

D
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

D, Thanks for the very informative reply. I'd completely forgotten that BB4W is zero-based, and will address that now. In the early days of programming, as far as I can remember, all the various dialects of Basic were 1-based. Returning to Basic recently, even though I program more modern languages remembering the zero, I certainly fell for it with BB4W.

Thanks for the comments about TKinter. I'll probably do both, for the comparison and the fun. Strangely, if I were to use a Basic for a program with a lot of screen material in it, I'd like to go back to QBasic, which could do a lot with screens very easily. Or how about iBasic? I loved that dialect, and still rue its demise.

My version of BB4W is 6.14a, by the way.