Bug 169883 - Natural order sort is unpredictable; need option to disable it
Summary: Natural order sort is unpredictable; need option to disable it
Status: RESOLVED FIXED
Alias: None
Product: dolphin
Classification: Applications
Component: general (show other bugs)
Version: 16.12.2
Platform: unspecified Linux
: NOR wishlist
Target Milestone: ---
Assignee: Peter Penz
URL:
Keywords:
: 179399 195004 197415 202372 205271 207051 217911 (view as bug list)
Depends on:
Blocks:
 
Reported: 2008-08-26 21:40 UTC by Felix
Modified: 2009-12-09 02:28 UTC (History)
13 users (show)

See Also:
Latest Commit:
Version Fixed In:


Attachments
Current sorting in Dolphin on top. Expected sorting in Dolphin below. (323.97 KB, image/jpeg)
2009-08-13 22:40 UTC, Michiel de Bruijne
Details
Correct sorting (Dolphin V1.3, KDE 4.3) (76.62 KB, image/png)
2009-08-14 00:04 UTC, Peter Penz
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Felix 2008-08-26 21:40:04 UTC
Version:            (using KDE 4.1.0)
Compiler:           arch linux binary package
OS:                Linux
Installed from:    Unlisted Binary Package

There are a few cases where natural order sort results in an unexpected and incorrect order. Example: hex filenames:

"Natural" order:

1a
1f
2a
21

Correct order:

1a
1f
21
2a

Example: filename jump by typing / quicksearch:

Suppose you have a list of files named

img-1
img-2
img-3
...
img-11
img-12
...
img-20
...
img-111

and you want img-111. A quick way to jump to it would be to start typing "img-111". With literal sorting, img-1 would be sufficient to jump to a cluster containing the desired file. With natural sorting, however, the files matching that prefix are widely separated and typing is not a viable way to jump to the desired file.

Examples from comments in Bug 87286 (whose resolution apparently introduced this problem in the first place :) ):

"If you represent data of binary trees in the following way:
filename0 --> First branch to the left
filename1 --> First branch to the right
filename01 --> First branch to the left, then right
filename10 --> First branch to the right, then left

Then the non-natural sorting would make more sense.

Also, if you don't seperate Version numbers by dots, the non-natural sorting
would be better:
filename2 --> Version 2
filename21 --> Version 2.1
filename3 --> Version 3"

Problem: since all shells use literal sorting, using natural sort in Konqueror means that the sorting orders will be different. This leads to confusion and possible errors by users.

Problem: Characters are ignored by sorting. Who judges which characters are "important enough" to include? (Characters ignored: space, !, ", #, $, %, &, ', (, ), *, +, ,(a comma), -, ., / and possibly others.)

Problem: Ignored characters are apparently overruled by numbers that occur much later in the filename, leading to such bizarre results as "2001-01-12" getting sorted before "!\"#$% la la la 2001-01-22"

Now the old trick of using ! or some other early character to guarantee a file will be at the top of a listing is no longer effective.


In summary, sorting used to be a definite, simply describable thing -- "it's sorted literally" was a phrase adequate to describe the algorithm.

Now, to have a mental picture of what the sorting will do involves memorizing something like "characters fall into three different classes: numbers [0-9], letters [A-Za-z], and other stuff. The sorting happens first on groups of numbers (or letters, if they come first). If other stuff occurs in the filename, it is largely ignored (sometimes). Letters are sorted normally, but *some* other stuff can still precede letters (but numbers always come before other stuff)."

Please provide an option to disable this -- just because Microsoft and Apple do something, doesn't mean it's a good idea. Natural sort gives me more "what the hell?" moments than it does "oh cool" ones.
Comment 1 Frank Reininghaus 2009-06-02 20:10:51 UTC
*** Bug 195004 has been marked as a duplicate of this bug. ***
Comment 2 ancow 2009-06-02 20:36:42 UTC
I would like to second the "option to disable it" idea. This kind of sorting is wildly unpredictable and extremely confusing to me (at least in some cases). While the idea behind natural order sorting is a nice one, the algorithm seems to need some work.
Comment 3 Felix 2009-06-03 02:08:12 UTC
I've just run into one more example where "natural order" basically means "random": a folder full of flickr filenames. Flickr filenames have the form "ddddddddd_hhhhhhhhh_suffix" where "d" are decimal digits and "h" are hex digits. This seems to confuse the hell out of natural order sort, and basically the files appear randomized and I can't find anything.

Please, please, add an option to turn this "feature" off.
Comment 4 Peter Penz 2009-06-03 07:40:20 UTC
@Felix: The report contains two separate issues. The issue mentioned in comment #3 (-> the handling of special characters) is a duplicate of bug 181211.

AFAIK there is no official definition of the term "natural sort order" - in the scope of KDE KStringHandler::naturalCompare() means that numbers are handled in a special way. Here it would be possible to add an option in Dolphin to turn it off.

However the sorting of strings (and parts of the string) which contain no numbers are delegated to a local aware comparing of Qt (-> the strings from comment #3 are sorted by Qt). Qt delegates this to glibc (see http://lists.kde.org/?l=kde-devel&m=124174284926086&w=2 for details) where a (in my opinion) wrong sorting is done.
Comment 5 Frank Reininghaus 2009-07-05 21:32:56 UTC
*** Bug 179399 has been marked as a duplicate of this bug. ***
Comment 6 doc.evans 2009-07-06 00:37:09 UTC
To try to be a bit more positive about this bug, since nothing seems to be happening with it the way it is currently presented to the developers: maybe it could be rephrased as a positive request to allow the user the (global) capability to have items presented in POSIX sort order?
Comment 7 FiNeX 2009-08-03 10:56:10 UTC
*** Bug 202372 has been marked as a duplicate of this bug. ***
Comment 8 Jörg 2009-08-03 21:18:34 UTC
I absolutely support comments #2, #3 and #6, but in the manner that "natural order" should be the option. 
Don't forget that all basics for software are well defined and understandable semantics, nice features can be based on this but not contrariwise.
Comment 9 Michiel de Bruijne 2009-08-13 22:38:22 UTC
Please change the severity back to normal (at least). See screenshot/attachment for current behavior. You cannot consider normal sorting a feature request for a file manager. Right?

B.T.W. I love Dolphin, but it makes it quite difficult to find back files.
Comment 10 Michiel de Bruijne 2009-08-13 22:40:23 UTC
Created attachment 36136 [details]
Current sorting in Dolphin on top. Expected sorting in Dolphin below.
Comment 11 Michiel de Bruijne 2009-08-13 22:45:18 UTC
Forgot to mention that this bug is still valid in KDE 4.3.0 (bug is registered for version KDE 4.1.0)
Comment 12 Peter Penz 2009-08-14 00:03:07 UTC
@Michiel (in reply to comment #10): Thanks for the screenshot, but I cannot reproduce this buggy behavior (see the attached screenshot using Dolphin for KDE 4.3). The order in your screenshot is definitely wrong and has nothing to do with "natural sorting". Can somebody else reproduce the behavior Michiel shows in the screenshot?
Comment 13 Peter Penz 2009-08-14 00:04:02 UTC
Created attachment 36137 [details]
Correct sorting (Dolphin V1.3, KDE 4.3)
Comment 14 Peter Penz 2009-08-14 00:11:32 UTC
@Michiel: I found the reason for your bug. It's a general issue in combination with the "Show in Groups" functionality. Items in the group "Others" are sorted in a wrong manner (see bug 173027) -> the issue is not related to "natural sorting".

I'll try to fix bug 173027 ASAP.
Comment 15 Michiel de Bruijne 2009-08-14 07:06:52 UTC
(In reply to comment #14)
> @Michiel: I found the reason for your bug. It's a general issue in combination
> with the "Show in Groups" functionality. Items in the group "Others" are sorted
> in a wrong manner (see bug 173027) -> the issue is not related to "natural
> sorting".
> 
> I'll try to fix bug 173027 ASAP.

---

Hi Peter,

I'm sorry for my comment on the wrong bug number. If you can fix bug 173027 then that would be fantastic. I have quite a lot of other files like the example I gave you and I would love to use Dolphin for these files. Thank you so much!

Best regards,
Michiel.
Comment 16 Ivan Ćurić 2009-08-17 21:44:56 UTC
I think there should be option to disable natural sort ordering.

Problems: it ignores characters like # _ and -.

I used trick of begining file name with # or _, so it is always first in directory. Now this doesn't work. In my Mp3 folder I have directory for each album, and I have directory "# Playlists". There is about 300 albums, so I want to quickly find my folder with playlists. But I can't any more. It is burried down there with folders starting with P.

Ignoring characters gets uglier. In one folder I keep all mp3s which don't belong to any album. This is sample from that folder:

Film - a blah.mp3
Film - b blah.mp3
Filmska muzika - a blah.mp3
Filmska muzika - b blah.mp3
Film - x blah.mp3
Film - y blah.mp3

I figured this is because it ignores " - " between atrist name and song name. To me this is very wrong. If I want to select all songs from artist "Film", I can't do it with one simple mouse move. I have to ctrl+click, or do it in two parts. In this sample, artist "Filmska muzika" has only two songs, but what if it has 30 songs. Than I would not even see that I didn't select all songs from artist "Film". That is bad. It could lead to accidental data loss.

There are more examples. My photo collection is organized into folders named something like this:

200901 - Stuff from home <- various photos taken during january
20090114 - Trip to somewhere
20090121 - Birthday party of someone

With natural ordering my folder "200901 - Stuff from home" is no longer listed with other folders from january 2009.

Defense of natural ordering is this example:

Image 1.jpg
Image 2.jpg
Image 10.jpg

but I think this is not very realistic. My digital camera (and every that I saw) will produce something more similar to this:

Image 000000001.jpg
Image 000000002.jpg
Image 000000010.jpg

so there is no need for natural sorting.

I searched web and I can't belive there is no option to disable this behavior. I read bug 179399 and bug 169883. I also read http://dolphin.kde.org/philosophy.html and http://sourcefrog.net/projects/natsort/ as someone sugested. One bug report you discarded as "not Target User Group". I think that I am your user target group. By Dolphin philosopy I am "Simon":
  * using computers last 14 years
  * employed in software developer company for last 5 years
  * advanced Windows XP user
  * Linux newbie - during college I was using some Unix and Linux systems, but this is my first Linux instalation in last 7 years. I installed openSuse 11.1 one month ago.

Another reason behind natural sorting is "other systems has it". I don't know about MacOS, but on WindowsXP there is option to disable it. That is all I am asking: option to disable this behavior. It doesn't need to have GUI. I am perfectly happy with editing some property file.

What bothers me most with this issue is Open/Save file dialogs. If I dont'n like Dolphin, I can find another file manager, but what will I do with Open/Save dialogs? In past 14 yers I learned all this little tricks of file handling, and now, you are breaking it without even giving option for old behavior. What I am supoused to do do? Rename all existing folders and files or forget about KDE?

P.S.
I registered in this tracking system just because of this issue, and spend whole evening writing this report so please reconsider your opinion.
Comment 17 Peter Penz 2009-08-17 22:31:43 UTC
Thanks Ivan for your detailed input. There are already quite a lot votes and reasoning for this wish and I'll provide an option to disable natural sorting until KDE 4.4. The option will be visible in the UI (no hidden option) and I'll also take care that it will be accessible in the file dialog. What I don't plan to offer is to have natural sort order and traditional sort order in parallel for different directories, so this will be just a global option (but I think this has not been requested anyhow by anyone).

One technical input: The ignoring of the characters -, _ and # has nothing to do with "natural sorting" in the sense as it has been implemented in kdelibs. It is an issue in Qt related to language aware comparing (see http://lists.kde.org/?l=kde-devel&m=124174284926086&w=2 for details). As turning off the natural sorting will also turn off language aware sorting this issue will also disappear.
Comment 18 Peter Penz 2009-08-18 00:04:11 UTC
I've just submitted a patch for review: http://reviewboard.kde.org/r/1350
Comment 19 Peter Penz 2009-08-26 20:36:35 UTC
A short update: The patch to fix this issue will be submitted on Monday the 31th of August (as changes in kdelibs are required, I've to wait until this date).
Comment 20 Peter Penz 2009-08-27 07:44:02 UTC
*** Bug 205271 has been marked as a duplicate of this bug. ***
Comment 21 Peter Paulsen 2009-08-27 12:08:04 UTC
And also related seem Bug 197415 and Bug 201101.
Comment 22 Peter Penz 2009-08-27 12:13:31 UTC
*** Bug 201101 has been marked as a duplicate of this bug. ***
Comment 23 Peter Penz 2009-08-27 12:15:07 UTC
*** Bug 197415 has been marked as a duplicate of this bug. ***
Comment 24 Peter Penz 2009-08-30 22:57:04 UTC
SVN commit 1017534 by ppenz:

Allow to turn off the natural sorting globally (see http://reviewboard.kde.org/r/1350).

BUG: 169883

 M  +11 -0     kdeui/kernel/kglobalsettings.cpp  
 M  +24 -1     kdeui/kernel/kglobalsettings.h  
 M  +44 -14    kfile/kdirsortfilterproxymodel.cpp  
 M  +5 -1      kfile/kdirsortfilterproxymodel.h  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1017534
Comment 25 Peter Penz 2009-08-30 22:58:57 UTC
SVN commit 1017536 by ppenz:

allow to turn off natural sorting

CCBUG: 169883

 M  +13 -1     behaviorsettingspage.cpp  
 M  +1 -0      behaviorsettingspage.h  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1017536
Comment 26 Janet 2009-08-31 12:17:54 UTC
Here http://reviewboard.kde.org/r/1350/ you are talking about a sorting order of image 10.jpg
image 11.jpg
image 1.jpg
image 2.jpg
when "natural" sorting is turned off.

But shouldn't that be
image 1.jpg
image 10.jpg
image 11.jpg
image 2.jpg
?

At least that's what I expect.
Comment 27 Dotan Cohen 2009-08-31 12:35:18 UTC
Thank you Peter!
Comment 28 Peter Penz 2009-08-31 14:15:53 UTC
@Janet: you are right and it is done as you expect :-)
Comment 29 Janet 2009-08-31 17:46:27 UTC
Thanks a lot!
Comment 30 markuss 2009-08-31 18:34:54 UTC
I'm a little bit confused. My bug 201101 was marked as duplicate of this here. In the other bug I requested that Dolphin should sort

text.txt
text2.txt

instead of the current sorting

text2.txt
text.txt

Now I read that this bug here is about sorting files as
image 1.jpg
image 10.jpg
image 11.jpg
image 2.jpg

But that's not at all what I requested. I didn't request a way to disable natural sorting, I requested a fix to natural sorting.
So why was my request marked as dupe?
Comment 31 Peter Penz 2009-09-01 08:13:10 UTC
@Markus: Sorry, this was my fault. I've reopened your wish.
Comment 32 Frank Reininghaus 2009-09-11 12:33:44 UTC
*** Bug 207051 has been marked as a duplicate of this bug. ***
Comment 33 cor 2009-09-11 13:38:38 UTC
I'm assuming we will be able to disable this on a per-folder basis, right?
Some places it's useful, some places not.
Comment 34 spir 2009-11-25 17:59:47 UTC
(In reply to comment #17)
> Thanks Ivan for your detailed input. There are already quite a lot votes and
> reasoning for this wish and I'll provide an option to disable natural sorting
> until KDE 4.4. The option will be visible in the UI (no hidden option) and I'll
> also take care that it will be accessible in the file dialog. What I don't plan
> to offer is to have natural sort order and traditional sort order in parallel
> for different directories, so this will be just a global option (but I think
> this has not been requested anyhow by anyone).
> 
> One technical input: The ignoring of the characters -, _ and # has nothing to
> do with "natural sorting" in the sense as it has been implemented in kdelibs.
> It is an issue in Qt related to language aware comparing (see
> http://lists.kde.org/?l=kde-devel&m=124174284926086&w=2 for details). As
> turning off the natural sorting will also turn off language aware sorting this
> issue will also disappear.

Thank you for this decision. Denis
Comment 35 Christoph Feck 2009-12-09 02:28:32 UTC
*** Bug 217911 has been marked as a duplicate of this bug. ***