Sort (structured) Linked list via multiple fields

[lexvictory]

I tried search, so sorry if this has come up before.

What I'm after is sorting of a structured linked list alphabetically (maybe one of the fields numerically too). multiple fields meaning sort by field one, then sort those that have the same field one so that they are in alphabetical order too.

Confusing explanation, so here's a demonstration:

Code: Select all

Structure item
title.s
artist.s
album.s
track.l
endstructure

Now, say the user wants it sorted by Album.
So we get (in title - artist - album format):

We Will Survive (2005 Live Mix) - Warp Brothers - Skitz Mix 23
Move Your Hands Up (Radio Edit) - Club Raiders - Skitz Mix 23
Whoa - We The Kings -We The Kings
Stay Young - We The Kings -We The Kings

You can see that the Titles are not in alphabetical order.

Is there a way to sort the list (in this example) by Album, then sort the Titles into alphabetical order within the albums, so we get:

Move Your Hands Up (Radio Edit) - Club Raiders - Skitz Mix 23
We Will Survive (2005 Live Mix) - Warp Brothers - Skitz Mix 23
Stay Young - We The Kings -We The Kings
Whoa - We The Kings -We The Kings

Sorting via another combination would also be preferred, eg. artist then title.
Is this possible? or would it involve making extra lists to do the second sorting?

[netmaestro]

There is an optional set of parameters to SortStructuredlist() - Start and End. So, try something like this:

1) Sort your list on the primary field
2) Step through the list with Foreach and keep a counter and a variable for lastprimary
3) Each time primary <> lastprimary, sort the list on secondary using your counter to know where starts and ends are

[lexvictory]

Thank you!
I've never used those parameters, so I didn't have a clue that it could be that easy...

Here what I whipped up, see any problems with it?

Code: Select all

    SortStructuredList(MemDB(), 2, #Offset_album, #PB_Sort_String)
    lastprimary = 0
    SelectElement(MemDB(), 0)
    lastprimary$ = MemDB()\album
    For x = 0 To ListSize(MemDB())-1
      If MemDB()\album <> lastprimary$
        SortStructuredList(MemDB(), 2, #offset_title, #PB_Sort_String, lastprimary, x-1)
        lastprimary = ListIndex(MemDB())
        lastprimary$ = MemDB()\album
      EndIf
    Next x

yes, I used the variable names too, couldn't think of a better name

[MrMat]

Another way is to have an extra string in the structure especially for sorting. Loop through the list once and set it to equal to e.g. artist + title for each element, then sort the list once by this string.

[freak]

Since PB 4.30, SortStructuredList (and SortList) use Mergesort which is a stable sort, so if you first sort all the list by titles and then again by album you will get a list which is sorted by album and each album is sorted by title.

Note that this does not work with Arrays, as SortArray uses Quicksort which is unstable. (ie the sorting of the secondary key would be lost)

[akj]

@ freak:

Please add to the Help documentation for SortStructuredList() and SortList() that they are stable sorts.

Is there any chance in the future for the other sort routines to have a stable sort option in addition to the standard method?

[technicorn]

@akj

It's not possible to use Mergesort for arrays, because Mergesort can't work in place, that means the array would have to be taken apart and then put back together again.

With lists you can use the already existend link headers of the list to do it.

For more in depth explanation use google and search for "Mergesort wiki"

[Trond]

But it's possible to make a stable quicksort.

[Little John]

It's not possible to use Mergesort for arrays, because Mergesort can't work in place, that means the array would have to be taken apart and then put back together again.

It is possible to use Mergesort for arrays, of course.

Regards, Little John