BugReport: not using a stable column sort algorithm (1 Viewer)

[Ger Hobbelt]

First off, kuddos for making an app where ID3TagIt went to see greener pastures.

How to reproduce issue:
A bug report in usability: open a directory (tree) with several mp3s in them. multiple artists, albums, etc.
Now click on the 'track', 'album' and 'artist' column headers -- in that order -- and you'ld expect an nicely ordered set of tracks, ordered per artist, then on album, and each track in sequential order within that album. (ID3TagIt does it like that ;-) )

Symptoms:
unfortunately, the above expected result is not what you get: the track and album columns are scrambled once you've done the sorting on artist. I don't need a look at the code to know you're probably using some quicksort implementation under the hood (which exhibits this behaviour). What should be done is picking another sort algorithm (which may be slower in the technical O(n log n) sense...) which is 'stable' so that you get the expected behaviour.

Why would you want the expected behaviour?
Because it helps a lot in quickly picking entire albums, or other sequences of tracks from a larger list, then apply actions to those tracks only, say 'organize', multi-track tag edit or 'case convert'.

Thanks for your efforts! Will be looking forward to any update!

 

[mbuzina]

Another hint: stay with quicksort, but remember the last n columns and sort by all of them (so your key will be artist|album|track). Usually 4-5 columns will be enough (sort genre|artist|album|cd|track is the longest I can imagine).

 

[hwahrmann]

Will have a look into it.

Not quite sure, if i am sorting myself, or if i use standard sorting stuff available in .Net Gridview

Edit: Yes, was doing my own sorting. almost forgot about it. Fixed it. next version will allow sorting on multi column

 

[Ger Hobbelt]

Another hint: stay with quicksort, but remember the last n columns and sort by all of them (so your key will be artist|album|track). Usually 4-5 columns will be enough (sort genre|artist|album|cd|track is the longest I can imagine).

A context-independent solution to stabilize quicksort (and other unstable sort algo's) is, before performing the sort operation, adding an extra column and fill it with a sequential number sequence (which would represent the current order of appearance of all rows), then do the qsort/whatever, where the sort criterium now includes that extra sequence column as the least significant key part.

In short: do not sort on (column) but on (column, seqid).

That way you don't have to 'remember' anything and it has perceived unlimited recall as any previous operations are all represented together through the temporary sequential number column.

This is a generic approach for when you don't know whether the sort code in use (a library call, mostly) is a stable or unstable algorithm.

 

[mbuzina]

Hi Ger. Good one, didn't know that approach (had no reason to yet ;-).