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

sorting integer arrays

Post by ArryMan »

Hi, I'm trying to get BB4W to sort an integer array. I think I've followed the blurb correctly, which specifically includes integer arrays for sorting. However, there is no smode% code given, they all relate to strings. I even tried smode% = 2, which relates to ascii characters, but that didn't work either.

Here's my code, loaded with a very small dummy array for test purposes. Any advice gratefully received. Thank you. :?
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

Whoops! Forgot the code! Here it is:

dir% = 0
smode% = 2
install @lib$+"SORTLIB"
sort% = fn_sortinit(dir%,smode%)

dim a%(5)

a%() = 39,2,7,144,5

for i = 1 to 5
print a%(i)
next i

call sort%, a%(0)

print
for i = 1 to 5
print a%(i)
MattC
Posts: 114
Joined: Mon 16 Apr 2018, 06:17

Re: sorting integer arrays

Post by MattC »

Hi ArryMan,

Not too familiar with SORTLIB, but depending on the speed you require and how many elements you are trying to sort, a simple method would be a bubble sort:

Code: Select all

      DIM A%(5)

      A%() = 39, 2, 7, 144, 5

      PRINT "Before:"
      FOR I% = 0 TO 5
        PRINT A%(I%)
      NEXT

      FOR I% = 4 TO 0 STEP -1
        FOR J% = 0 TO I%
          IF A%(J%) > A%(J% + 1) THEN
            T% = A%(J%)
            A%(J%) = A%(J% + 1)
            A%(J% + 1) = T%
          ENDIF
        NEXT
      NEXT

      PRINT "After:"
      FOR I% = 0 TO 5
        PRINT A%(I%)
      NEXT
(Note: in case you're unaware, elements of an array start at zero)

With just a few element the speed is negligible. However, as the number of elements increases, the number of passes required (and therefore the time taken) increases exponentially. (On my computer the example above took no time at all; a thousand elements took 0.2 sec; 10000 took 20 sec. I didn't go any further.)

Not sure if this helps, or if anyone else has a better solution. (Not quite as familiar with binary sorts.)

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

Re: sorting integer arrays

Post by ArryMan »

Thanks, Matt, is that the famous bubble sort?
MattC
Posts: 114
Joined: Mon 16 Apr 2018, 06:17

Re: sorting integer arrays

Post by MattC »

'Sort' of. :lol:
ArryMan
Posts: 12
Joined: Sat 05 Feb 2022, 10:59

Re: sorting integer arrays

Post by ArryMan »

Ha ha! Very punny (er, puny)! :lol:
DDRM

Re: sorting integer arrays

Post by DDRM »

Hi Arryman,

You might find it useful to look at the "sorttest" example in the "general" folder of the examples. It looks like using smode%=&1000 is the domino of choice, unless you have specific string sorting requirements. Does that work?

Bubble sorts are easy to visualise and code, but are spectacularly slow for more than quite modest numbers of items....

Best wishes,

D
MattC
Posts: 114
Joined: Mon 16 Apr 2018, 06:17

Re: sorting integer arrays

Post by MattC »

DDRM wrote: Sun 06 Feb 2022, 17:14 Bubble sorts are easy to visualise and code, but are spectacularly slow for more than quite modest numbers of items....
This definitely follows my experimentation. For each additional element, the routine has to perform that number of additional loops (less one). So a single increase of the number of elements from, say, 9 to 10, would require an additional 9 loops - a small number. However, a single increase from 999,999 to 1,000,000 would require an additional 999,999 loops - not to be sniffed at. With the number of elements this high, one could go 'loopy'. :roll:

Arryman, on a more serious note, I think I found the problem. Re-reading the help on 'Sorting Data Arrays', I noticed you hadn't added the line preceding the CALL. You need the lines:

Code: Select all

C% = DIM(array(),DIM(array()))+1
CALL sort%, array(0)
or

Code: Select all

C% = DIM(array(),DIM(array()))
CALL sort%, array(1)
... depending on which element you want to start with. The help explains more fully. Note the 'C% = ' and the call's array's element index.

Hope this helps.

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

Re: sorting integer arrays

Post by ArryMan »

Matt, thanks a lot, that clears things up. In the meantime, I decided to write my own routine instead of pinching yours. The main difference is in the use of the SWAP function, which shortens 3 lines to one. Here's my offering:

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

Just pass an array a% into it and it does the rest, including finding out the size of the array for itself. I agree that this can be a very inefficient method, but my arrays here are quite small, so it doesn't matter in this instance.
MattC
Posts: 114
Joined: Mon 16 Apr 2018, 06:17

Re: sorting integer arrays

Post by MattC »

Interesting.

The SWAP command does speed up the routine by around 20-25%. (Although, it's funny, but I tried using that the first time I looked at this thread and, for some reason, it didn't work. So I just did a standard swap. Tried again, and 'hey presto'...)

However, it looks like your routine misses out on the inner (or outer loop) which is necessary. It is true that there is a WHILE loop, but this does not do any counting as such. The 'bubble' need to run though the list, more-or-less, from start to finish at least once for each element. (This is not quite true, which is why there is one less than the number of elements in the outer loop and a gradual reduction in the recursive loop.) Set up some test data for your routine and try it out. When I did, all I got was the last number repeated throughout. (Unless I was doing something wrong with your routine.)

The idea of finding the array size is a good one, and could possibly used in a library routine.

Matt