Buggy sort

[Nicolas Rybkin]

There's a problem when unsorted sort order is chosen. When I choose 
undsorted when I've already entered directory it displays list properly, but 
when I enter directory with (sort order = unsorted) it often (not for every 
dir) displays the first entry of the list last and the last first. It seems 
that the number of entries in the dir doesn't matter.
When I comment qsort() call in dir.c everything is OK (except other sort orders 
don't work, of course).
Here's sort routine for unsorted:
int
unsorted (file_entry_t * a, file_entry_t * b)
{
(void) a;
(void) b;
return 0;
}
So it seems to be OK.
Here's qsort() call:
qsort ((list-list)[dot_dot_found], list-len - dot_dot_found, sizeof 
(file_entry_t), sort);
dot_dot_found seems doesn't matter. So I have no idea what's wrong, maybe bug 
in qsort. I'm going to make a change that qsort() won't be called if sort order 
== unsorted.  But maybe anyone has any ideas? This issue is really important 
to me.
___
mc-devel mailing list
https://mail.gnome.org/mailman/listinfo/mc-devel

Re: Buggy sort

[Yury V. Zaytsev]

On Tue, 2015-06-30 at 00:46 +0300, Nicolas Rybkin wrote:
 But maybe anyone has any ideas? This issue is really important to me.

Nicolas,

Wow, hats off for the discovery and analysis. Could you please specify
on which platform you are running mc, which C library are you using,
etc.?

As you saw, the unsorted order has been implemented by passing a sort
routine that simply compares equal for all elements to qsort.

However, quicksort by definition is not a *stable* sorting algorithm,
which means that there is no guarantee that the order of the elements is
preserved if all elements compare equal for efficient implementations of
qsort. That is, in theory, qsort is allowed to return some permutation
of elements if they compare equal, like in our case, and certainly can
swap first and last elements if they are equal at will.

Of course, in practice, quicksort is often implemented to be mostly
stable such that this kind of random shuffling is not happening on
purpose when it's not absolutely required for performance.

Therefore, frankly speaking, I'm very baffled by your post. It seems
that you were able to find a platform that implements quicksort so
efficiently as to make it unstable for some lists, and also found some
file lists that trigger the re-ordering...

...unless your analysis is incorrect and a problem is in reality
somewhere else :-)

So, it would be great if you'd post some more details (see above,
platform, libc and list of files), so that I and/or Andrew can possibly
reproduce it. The best way would be to marshal the list of file_entry_t
to a file and make sure this qsort issue happens outside of mc, but I
understand that this could be too much work for you...

The number one question here for me would be, could it be some
off-by-one bug, as in are all other sorts working correctly on these
directories in all cases, and my theory above is correct?

-- 
Sincerely yours,
Yury V. Zaytsev


___
mc-devel mailing list
https://mail.gnome.org/mailman/listinfo/mc-devel