Page 1 of 1
Sort (structured) Linked list via multiple fields
Posted: Tue Dec 30, 2008 10:23 am
by 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?
Posted: Tue Dec 30, 2008 10:33 am
by 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
Posted: Tue Dec 30, 2008 11:17 am
by 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
Posted: Tue Dec 30, 2008 12:13 pm
by 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.
Posted: Tue Dec 30, 2008 3:14 pm
by 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)
Posted: Tue Dec 30, 2008 6:06 pm
by 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?
Posted: Sun Jan 04, 2009 3:55 pm
by 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"
Posted: Sun Jan 04, 2009 3:59 pm
by Trond
But it's possible to make a stable quicksort.
Posted: Thu Jan 22, 2009 4:47 pm
by Little John
technicorn wrote: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