• Sorting algorithms

    From Bob Latham@bob@sick-of-spam.invalid to comp.sys.acorn.programmer on Fri Nov 6 08:45:15 2026
    From Newsgroup: comp.sys.acorn.programmer

    A music library scan tool I've written produces a list of over 4000
    lines, each line shows the path to a particular album. But the filer
    does not list in alphabetic order...

    There are two sort types I understand; Bubble sort and what I call
    "Best So Far" but I bet there is a different official name.

    I've always gone for bubble sort for two reasons, firstly I
    understand the principle and it does not require another chunk of ram
    to hold the result file. But using this method takes 12.6 seconds.

    The "Best So Far" method is to repeatedly pass through the source
    file and pick out the best line on each pass and move it out to
    another store and mark it as used in the source. I had the idea of
    squirting these best lines one at a time to a file on disc rather
    than provide temporary ram.

    I realised that using OS_BPut, line by line was not going to be as
    fast as saving a file in one go but tried it anyway. It took 6
    seconds. Faster yes but I don't like it, the sorted file never exists
    in the application. True it doesn't matter but it kind of does to me.

    Anyone got any suggestions for a better approach? Something I might
    even understand?

    A slight complication, any sort would need to handle is the Coline
    Dion problem. I like treating o as e as regards the sort comparison
    stage.

    Also, how is StrongEd so lightning fast on sorts? It barely blinks.


    Still coded in Basic Assembler, in case you need to know.


    Thanks.

    Bob.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Jean-Michel@jmc.bruck@orange.fr to comp.sys.acorn.programmer on Fri Nov 6 17:30:51 2026
    From Newsgroup: comp.sys.acorn.programmer

    In message <5d336712aebob@sick-of-spam.invalid>
    Bob Latham <bob@sick-of-spam.invalid> wrote:

    A music library scan tool I've written produces a list of over 4000
    lines, each line shows the path to a particular album. But the filer
    does not list in alphabetic order...
    ???
    Is the list a text file?

    There are two sort types I understand; Bubble sort and what I call
    "Best So Far" but I bet there is a different official name.

    I've always gone for bubble sort for two reasons, firstly I
    understand the principle and it does not require another chunk of ram
    to hold the result file. But using this method takes 12.6 seconds.

    The "Best So Far" method is to repeatedly pass through the source
    file and pick out the best line on each pass and move it out to
    another store and mark it as used in the source. I had the idea of
    squirting these best lines one at a time to a file on disc rather
    than provide temporary ram.

    I realised that using OS_BPut, line by line was not going to be as
    fast as saving a file in one go but tried it anyway. It took 6
    seconds. Faster yes but I don't like it, the sorted file never exists
    in the application. True it doesn't matter but it kind of does to me.

    Anyone got any suggestions for a better approach? Something I might
    even understand?

    A slight complication, any sort would need to handle is the Coline
    Dion problem. I like treating o as e as regards the sort comparison
    stage.
    Thanks for Coline :-)

    Also, how is StrongEd so lightning fast on sorts? It barely blinks.
    Yes, but failed with Coline...
    with capital letters Coline => C+LINE, ko too

    Still coded in Basic Assembler, in case you need to know.
    good luck!

    Thanks.

    Bob.
    --
    Jean-Michel
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Bob Latham@bob@sick-of-spam.invalid to comp.sys.acorn.programmer on Fri Nov 6 17:57:58 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <1db391335d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:
    In message <5d336712aebob@sick-of-spam.invalid>
    Bob Latham <bob@sick-of-spam.invalid> wrote:

    But the filer does not list in alphabetic order...

    ??? Is the list a text file?

    Yes.


    Bob.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Jean-Michel@jmc.bruck@orange.fr to comp.sys.acorn.programmer on Fri Nov 6 20:28:40 2026
    From Newsgroup: comp.sys.acorn.programmer

    In message <5d3399acf0bob@sick-of-spam.invalid>
    Bob Latham <bob@sick-of-spam.invalid> wrote:

    In article <1db391335d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:
    In message <5d336712aebob@sick-of-spam.invalid>
    Bob Latham <bob@sick-of-spam.invalid> wrote:

    But the filer does not list in alphabetic order...

    ??? Is the list a text file?

    Yes.
    I did some tests with C/C++ fonctions, result(s) not good with "Coline" problem.
    Only Datapower gave me the good order...
    Not tested with Fireworkz!





    Bob.
    --
    Jean-Michel
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Paul Sprangers@Paul@sprie.nl to comp.sys.acorn.programmer on Sat Nov 7 13:36:33 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <5d336712aebob@sick-of-spam.invalid>,
    Bob Latham <bob@sick-of-spam.invalid> wrote:
    A music library scan tool I've written produces a list of over 4000
    lines, each line shows the path to a particular album. But the filer
    does not list in alphabetic order...

    My own database program uses SYS "OS_HeapSort". It sorts a block of 4000 strings in less than a fraction of a second, inluding the routine that
    takes capitals, diacritics and other signs into account. A perfect job,
    but... quite some programming is involved.

    Paul
    --
    https://riscos.sprie.nl
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Jean-Michel@jmc.bruck@orange.fr to comp.sys.acorn.programmer on Sat Nov 7 18:55:13 2026
    From Newsgroup: comp.sys.acorn.programmer

    In message <5d340015eePaul@sprie.nl>
    Paul Sprangers <Paul@sprie.nl> wrote:

    In article <5d336712aebob@sick-of-spam.invalid>,
    Bob Latham <bob@sick-of-spam.invalid> wrote:
    A music library scan tool I've written produces a list of over 4000
    lines, each line shows the path to a particular album. But the filer
    does not list in alphabetic order...

    My own database program uses SYS "OS_HeapSort". It sorts a block of 4000 strings in less than a fraction of a second, inluding the routine that
    takes capitals, diacritics and other signs into account. A perfect job, but... quite some programming is involved.

    Paul

    Nice,You have implemented your own routine in ASM , many characteristics
    to take into account, not easy.
    --
    Jean-Michel
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Paul Sprangers@Paul@sprie.nl to comp.sys.acorn.programmer on Sat Nov 7 19:41:43 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <91421d345d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:

    Nice,You have implemented your own routine in ASM

    No, I wrote the entire program in BASIC and then compiled it with !ABC.
    But of course, OS_HeapSort does the actual sorting. My routines just
    prepare the strings. Remember however that OS_HeapSort only sorts memory blocks, it won't do anything with arrays - as far as I remember.

    Paul
    --
    https://riscos.sprie.nl
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Martin@News04@avisoft.f9.co.uk to comp.sys.acorn.programmer on Sat Nov 7 19:48:00 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <5d34218484Paul@sprie.nl>,
    Paul Sprangers <Paul@sprie.nl> wrote:
    In article <91421d345d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:

    Nice,You have implemented your own routine in ASM

    No, I wrote the entire program in BASIC and then compiled it with
    !ABC. But of course, OS_HeapSort does the actual sorting. My
    routines just prepare the strings. Remember however that
    OS_HeapSort only sorts memory blocks, it won't do anything with
    arrays - as far as I remember.

    The ArmSort module will happily sort one or more BASIC arrays (see www.avisoft.f9.co.uk) ... but it does not cater for the Coline problem
    without creating a duplicate array with the accent removed.
    --
    Martin Avison
    Note that unfortunately this email address will become invalid
    without notice if (when) any spam is received.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Bob Latham@bob@sick-of-spam.invalid to comp.sys.acorn.programmer on Sun Nov 8 12:13:58 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <5d34279617News04@avisoft.f9.co.uk>,
    Martin <News04@avisoft.f9.co.uk> wrote:
    In article <5d34218484Paul@sprie.nl>,
    Paul Sprangers <Paul@sprie.nl> wrote:
    In article <91421d345d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:

    Nice,You have implemented your own routine in ASM

    No, I wrote the entire program in BASIC and then compiled it with
    !ABC. But of course, OS_HeapSort does the actual sorting. My
    routines just prepare the strings. Remember however that
    OS_HeapSort only sorts memory blocks, it won't do anything with
    arrays - as far as I remember.

    The ArmSort module will happily sort one or more BASIC arrays (see www.avisoft.f9.co.uk) ... but it does not cater for the Coline
    problem without creating a duplicate array with the accent removed.

    Thanks everyone for you thoughts and ideas. My best code takes 6
    seconds but it does handle the Coline problem and it looks like a
    major effort to improve it unfortunately. Sorry I've been slow to
    return I've had an unpleasant virus for a couple of days.

    Thanks.

    Bob.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Paul Sprangers@Paul@sprie.nl to comp.sys.acorn.programmer on Wed Nov 11 17:06:45 2026
    From Newsgroup: comp.sys.acorn.programmer

    I've written a short BASIC program that sorts the lines in a text file,
    taking capitals, undercasts and all sorts of diacritics, as well most other characters into account.

    My own example has nearly 6000 lines.
    The BASIC version took about 23 seconds to sort them, while the compiled version took less than 3 seconds to do the job. (On a 4to2 computer.)

    The text file is not included, but you should rename yours to "Texts" in
    order to let the program do its work. If your text file counts more than
    6000 lines, you should change the DIM's in the program. Compile the program with the freely available !ABC compiler. Remember that the compiled version needs quite a big NEXT slot.

    There are much better or memory friendly ways to do this, but as an example
    it may have some use.

    Paul



    REM DIM two string arrays,
    REM big enough to store your lines.
    REM My example had 5913 lines.

    DIM text$(5913), dummy$(5913)

    REM Now store every line into both arrays.
    REM The dummy array will be adjusted on the fly,
    REM by changing undercast into capitals and by
    REM removing diacritics, in FNcase (see botom).

    f%=OPENIN("Texts")
    IF f%>0 THEN
    a%=0
    REPEAT
    a%+=1
    text$(a%) = GET$#f%
    dummy$(a%) = FNcase(text$(a%))
    UNTIL EOF#f%
    ENDIF
    IF f%>0 THEN CLOSE#f%

    REM NOW the actual sorting will start

    OK% = TRUE
    time = TIME

    PROCsort

    t = TIME - time : REM The time needed in centiseconds.

    REM Finally, print the sorted lines

    FOR i% = 1 TO a% : PRINT STR$(i%) +": " + text$(i%) : NEXT
    PRINT t
    END


    DEF PROCsort
    FOR i% = 1 TO a%
    IF dummy$(i%) < dummy$(i%-1) THEN
    SWAP text$(i%),text$(i%-1)
    SWAP dummy$(i%),dummy$(i%-1)
    OK% = FALSE
    ENDIF
    NEXT
    IF NOT OK% THEN OK% = TRUE : PROCsort
    ENDPROC


    DEF FNcase(x$)
    y$=""
    FOR j%= 1 TO LEN x$
    c%=ASC(MID$(x$,j%,1))
    IF c%>96 AND c%<123 THEN y$ += CHR$(c%-32) : REM undercast -> capital
    IF c%>47 AND c%< 58 THEN y$ += CHR$(c%) : REM numbers don't change
    IF c%>64 AND c%< 91 THEN y$ += CHR$(c%) : REM capitals don't change
    IF c%>223 AND c%<230 THEN y$ += "A" : REM diacritics removed
    IF c%>231 AND c%<231 THEN y$ += "E"
    IF c%>235 AND c%<240 THEN y$ += "I"
    IF c%>241 AND c%<247 THEN y$ += "O"
    IF c%>248 AND c%<253 THEN y$ += "U"
    IF c%=229 OR c%=197 THEN y$ += "A"
    IF c%=230 OR c%=198 THEN y$ += "AE"
    IF c%=231 OR c%=199 THEN y$ += "C"
    IF c%=241 OR c%=209 THEN y$ += "N"
    IF c%=248 OR c%=216 THEN y$ += "O"
    IF c%=223 THEN y$ += "SS"
    IF c%=255 THEN y$ += "Y"
    NEXT
    =y$
    --
    https://riscos.sprie.nl
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Martin@News04@avisoft.f9.co.uk to comp.sys.acorn.programmer on Wed Nov 11 17:14:34 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <5d3622ac84Paul@sprie.nl>,
    Paul Sprangers <Paul@sprie.nl> wrote:
    I've written a short BASIC program that sorts the lines in a text
    file, taking capitals, undercasts and all sorts of diacritics, as
    well most other characters into account.

    My own example has nearly 6000 lines. The BASIC version took about
    23 seconds to sort them, while the compiled version took less than
    3 seconds to do the job. (On a 4to2 computer.)

    The text file is not included, but you should rename yours to
    "Texts" in order to let the program do its work. If your text file
    counts more than 6000 lines, you should change the DIM's in the
    program. Compile the program with the freely available !ABC
    compiler. Remember that the compiled version needs quite a big NEXT
    slot.

    There are much better or memory friendly ways to do this, but as an
    example it may have some use.

    [Snip]

    As a specific example, it works but does have some limitations.
    The most obvious one is that any characters not included in FNcase are
    omitted from the sort key completely (eg blank or hyphen). This may be deliberate, but means it is not a plain sort.

    If you load the ArmSort module, then PROCsort can be replaced simply
    by the line
    *Sort 1 a% dummy$(n) text$(e)
    which probably saves time and effort.

    The *Sort command may mean ABC cannot compile it, but I would be
    interested to hear how the time compared without compilation.
    I suspect however that as FNcase tests each character 29 times, it
    could be optimised.

    Martin
    --
    Martin Avison
    Note that unfortunately this email address will become invalid
    without notice if (when) any spam is received.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Paul Sprangers@Paul@sprie.nl to comp.sys.acorn.programmer on Wed Nov 11 19:25:34 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <5d3628e1b7News04@avisoft.f9.co.uk>,
    Martin <News04@avisoft.f9.co.uk> wrote:

    As a specific example, it works but does have some limitations.
    The most obvious one is that any characters not included in FNcase are omitted from the sort key completely (eg blank or hyphen).

    You're right, Martin. But it is deliberate indeed. I should have mentioned
    that the program sorts lines *alphabetically*, reason why it omits
    characters like spaces, hyphens, dots, colons etc. completely.

    I also left out ArmSort, because I wanted to show code that does it all by
    its self.

    I suspect however that as FNcase tests each character 29 times, it could
    be optimised.

    Absolutely. My database program sorts the same 6000 lines in a fraction of
    a second, font painting the result on screen included. But hm... I should
    wade through the rivers of code for finding out how I did that. And even
    then I'm afraid that I would no longer understand it.
    Oh youth, thou treacherous promise!

    Paul
    --
    https://riscos.sprie.nl
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Jean-Michel@jmc.bruck@orange.fr to comp.sys.acorn.programmer on Wed Nov 11 20:36:03 2026
    From Newsgroup: comp.sys.acorn.programmer

    In message <5d3622ac84Paul@sprie.nl>
    Paul Sprangers <Paul@sprie.nl> wrote:

    I've written a short BASIC program that sorts the lines in a text file, taking capitals, undercasts and all sorts of diacritics, as well most other characters into account.

    My own example has nearly 6000 lines.
    The BASIC version took about 23 seconds to sort them, while the compiled version took less than 3 seconds to do the job. (On a 4to2 computer.)

    The text file is not included, but you should rename yours to "Texts" in order to let the program do its work. If your text file counts more than
    6000 lines, you should change the DIM's in the program. Compile the program with the freely available !ABC compiler. Remember that the compiled version needs quite a big NEXT slot.

    There are much better or memory friendly ways to do this, but as an example it may have some use.

    Paul



    REM DIM two string arrays,
    REM big enough to store your lines.
    REM My example had 5913 lines.

    DIM text$(5913), dummy$(5913)

    REM Now store every line into both arrays.
    REM The dummy array will be adjusted on the fly,
    REM by changing undercast into capitals and by
    REM removing diacritics, in FNcase (see botom).

    f%=OPENIN("Texts")
    IF f%>0 THEN
    a%=0
    REPEAT
    a%+=1
    text$(a%) = GET$#f%
    dummy$(a%) = FNcase(text$(a%))
    UNTIL EOF#f%
    ENDIF
    IF f%>0 THEN CLOSE#f%

    REM NOW the actual sorting will start

    OK% = TRUE
    time = TIME

    PROCsort

    t = TIME - time : REM The time needed in centiseconds.

    REM Finally, print the sorted lines

    FOR i% = 1 TO a% : PRINT STR$(i%) +": " + text$(i%) : NEXT
    PRINT t
    END


    DEF PROCsort
    FOR i% = 1 TO a%
    IF dummy$(i%) < dummy$(i%-1) THEN
    SWAP text$(i%),text$(i%-1)
    SWAP dummy$(i%),dummy$(i%-1)
    OK% = FALSE
    ENDIF
    NEXT
    IF NOT OK% THEN OK% = TRUE : PROCsort
    ENDPROC


    DEF FNcase(x$)
    y$=""
    FOR j%= 1 TO LEN x$
    c%=ASC(MID$(x$,j%,1))
    IF c%>96 AND c%<123 THEN y$ += CHR$(c%-32) : REM undercast -> capital
    IF c%>47 AND c%< 58 THEN y$ += CHR$(c%) : REM numbers don't change
    IF c%>64 AND c%< 91 THEN y$ += CHR$(c%) : REM capitals don't change
    IF c%>223 AND c%<230 THEN y$ += "A" : REM diacritics removed
    IF c%>231 AND c%<231 THEN y$ += "E"
    IF c%>235 AND c%<240 THEN y$ += "I"
    IF c%>241 AND c%<247 THEN y$ += "O"
    IF c%>248 AND c%<253 THEN y$ += "U"
    IF c%=229 OR c%=197 THEN y$ += "A"
    IF c%=230 OR c%=198 THEN y$ += "AE"
    IF c%=231 OR c%=199 THEN y$ += "C"
    IF c%=241 OR c%=209 THEN y$ += "N"
    IF c%=248 OR c%=216 THEN y$ += "O"
    IF c%=223 THEN y$ += "SS"
    IF c%=255 THEN y$ += "Y"
    NEXT
    =y$

    Interesting, good ASCII table usage.
    Just a little error, for E "diacritics", sorry I am French, we have many.

    IF c%>231 AND c%<231 THEN y$ += "E"
    => IF c%>231 AND c%<236 THEN y$ += "E"

    I am waiting the same for UTF8...
    --
    Jean-Michel
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Paul Sprangers@Paul@sprie.nl to comp.sys.acorn.programmer on Wed Nov 11 22:55:49 2026
    From Newsgroup: comp.sys.acorn.programmer

    In article <bdd535365d.jmb@jmc.bruck.orange.fr>,
    Jean-Michel <jmc.bruck@orange.fr> wrote:

    IF c%>231 AND c%<231 THEN y$ += "E"
    => IF c%>231 AND c%<236 THEN y$ += "E"

    Well spotted! Silly typo of mine.

    I am waiting the same for UTF8...

    Don't hold your breath...

    Paul
    --
    https://riscos.sprie.nl
    --- Synchronet 3.22a-Linux NewsLink 1.2