sort an array

[Brian White]

The classic (aka simple, aka not super fast) bubble sort is simple enough
to write in fp in just a few lines.

I have a routine that sorts a directory listing. Here the array that needs
to be sorted is dirl[]. It's an array of filenames in no order.

The starting conditions are:

* dirl[] is dimmed larger than I think I am likely to need at run-time.
2048 elements, 32 bytes each in my case.

* dirl[] has been loaded with some number of items. It might be anywhere
from 0 to 2048.

* n is the number of items that were loaded, 0 to 2048.

(reasons later)

Then I gosub bsrt, and after that dirl[] is sorted.


Aside from dirl[] and n, it requires a 2nd array that's the same size &
structure as the one you're sorting and 2 scratch variables for counters
that are all only used within the gosub, IE you can re-use them for other
stuff before and after the gosub. Those are tmpl[], i, and r here.

This is pretty much a direct translation of the optimized bubble sort
pseudo-code right from the wikipedia entry describing the logic, and some
BASIC version I found somewhere.

In MY case, just to show the real example, the array dirl[], and count/size
n, are filled by:
       ◆ If:
       Then: n=opendir("*",d{"") ;i="1"
cpd    ◆ If: i le n
       Then: dirl[i]=@DIRLIST_FILENAME[i] ;i=i+"1" ;goto cpd
       Then: x=closedir()

So I have an array that has 2048 elements, and N that says I only care
about elements 1-to-N. (Well, N can actually be 0 at run-time, that's
handled too.)


And finally the gosub:

       ◆ If: 'directory list    ;temp copy for bubble sort
       Then: dim dirl[2048](32) ;dim tmpl[2048](32)
bsrt   ◆ If: '***  bubble sort dirl[]  ***
       Then: i="1"
bsi    ◆ If:
       Then: r="1"
bsr    ◆ If: dirl[r] gt dirl[r+"1"]
       Then: tmpl[r]=dirl[r] ;dirl[r]=dirl[r+"1"] ;dirl[r+"1"]=tmpl[r]
       ◆ If: r lt n-i
       Then: r=r+"1" ;goto bsr
       ◆ If: i lt n
       Then: i=i+"1" ;goto bsi
       ◆ If:
       Then: return 'bsrt



Explanation of some of it:

Why the N?
We can't dim a variable sized array on the fly at run-time, and the size of
the array matters a lot in a bubble sort, because it has to pass over all
the items over and over again, only reducing the list size by one each
time. It takes several seconds to sort even a few hundred items let alone
2k. And it's not a linear progression, 200 items takes a lot longer than
twice as much as 100 items. And whatever size you dim, you need a 2nd copy
of the same array during the sort. So you dim an array that's hopefully
larger than you will need at run-time just to allow for the worst case, yet
as small as you can get away with, and then when you fill the array, you
keep a count of how many elements you **actually** used in N, and then
everywhere else you deal with the array, only count up to N.

The loop counts from 1 to N, yet N=0 is hanlded too
In the case of N=0, the gosub would do one pointless compare/copy of
dirl[1] and tmpl[1] and immediately return. The data in dirl[1] and dirl[2]
will have been modified because the first item in the first pass gets
compared and copied before discovering that 1 is already more than N, but
nothing should care about that. None of the data anywhere in dirl[] matters
whenever N is zero. It's either blank, or leftover from some previous
iteration of a loop or gosub or @key etc. And that one compare doesn't cost
anything, ie it's not even like a single pass over the 2048 items, it's
barely more work than doing a test to see if n is 0 as a special case test
before going into the loop in the first place.)



-- 
bkw



On 06/05/2018 11:26 AM, Richard D. Williams via Filepro-list wrote:

Dave,

I don't know of any function in FP that will sort an array.

What I do is write the array data out to a temporary file that has an index
built in the correct order,
clear the array, reach back into the temporary file, and fill the array
again.

You can use the tty as a unique identifier for each instance.

Hope this helps,

Richard


On 6/5/2018 9:28 AM, davidrottkamp via Filepro-list wrote:

Hi

Is there a way to sort an array made inside filepro

version

linux



_______________________________________________
Filepro-list mailing list
Filepro-list at lists.celestial.com
Subscribe/Unsubscribe/Subscription Changes
http://mailman.celestial.com/mailman/listinfo/filepro-list



-- 
bkw
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.celestial.com/pipermail/filepro-list/attachments/20180606/b60bb08e/attachment.html>