sorting integer arrays

[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]

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]

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]

Thanks, Matt, is that the famous bubble sort?

[MattC]

'Sort' of.

[ArryMan]

Ha ha! Very punny (er, puny)!

[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]

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'.

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]

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]

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