interesting task for .NET learners: why ArrayList.Sort hangs? [.NET 1.1]

[Wiktor Zychla [C# MVP]]

Following code was supposed to sort an ArrayList of strings while keeping
one "fixed" element at the last position.
However, the code hangs in .NET 1.1. I think that answering these questions
should be an interesting and instructive task for .NET learners:

1. why the code hangs in .NET 1.1?
2. why it does not hang in .NET 2.0?
3. why it does not hang in .NET 1.1 when you keep the "fixed" element at the
first (instead of last) position:

if ( ys == "fixed" )
return 1;
if ( xs == "fixed" )
return -1;

4. how to fix the code of the comparer so that sorting works in .NET 1.1?

Regards,
Wiktor Zychla

using System;
using System.Collections;

class TestComparer : IComparer
{
public int Compare(object x, object y)
{
if (!( x is string )) return 0;
if (!( y is string )) return 0;

string xs = x as string;
string ys = y as string;

if ( ys == "fixed" )
return -1;
if ( xs == "fixed" )
return 1;

return xs.CompareTo( ys );
}
}

class Test
{
public static void Main()
{
ArrayList test = new ArrayList();

test.Add( "test2" );
test.Add( "test1" );
test.Add( "fixed" );
test.Add( "test5" );
test.Add( "test4" );
test.Add( "test3" );

foreach ( string s in test )
Console.WriteLine( s );

Console.WriteLine();
test.Sort( new TestComparer() );

foreach ( string s in test )
Console.WriteLine( s );
}
}

 

[Jon Skeet [C# MVP]]

Following code was supposed to sort an ArrayList of strings while keeping
one "fixed" element at the last position.
However, the code hangs in .NET 1.1. I think that answering these questions
should be an interesting and instructive task for .NET learners:

Does that mean you're rather that people who aren't newbies don't
answer?

Jon

 

[Wiktor Zychla [C# MVP]]

Does that mean you're rather that people who aren't newbies don't

answer?

it depends on whether the answer is obvious to you or not. if it is - let
others think and find the answer by themselves.

there are no prizes for correct answers

Wiktor

 

[Jon Skeet [C# MVP]]

it depends on whether the answer is obvious to you or not. if it is - let
others think and find the answer by themselves.

there are no prizes for correct answers

No problem. I wasn't sure whether you were actually interested in the
answer or whether you were *just* posing it as a training question.

Jon

 

[Chris S.]

a bug in the quicksort in 1.1? seems to only happen with "fixed" which
is bizzarre

 

[Jon Skeet [C# MVP]]

a bug in the quicksort in 1.1? seems to only happen with "fixed" which
is bizzarre

I'm not sure whether I'd classify it as a bug in 1.1. Hint: if you give
2.0 different data (still just strings) but the same comparison method
you can break that, too - although it throws an exception rather than
hanging.

Jon

 

[Marc Gravell]

As Jon said - it's nothing (really) to do with 1.1

IIRC, a while back I did actually have this very issue in production code
once (something that slipped through review) - once you see it, it's a
forehead-slapping moment - and usually one you remember... ;-p

Marc

 

[Chris S.]

My second attempt: the -1 and 1 return values are the wrong way round
so the sort ends up recreating the the array indefinitely

 

[Jon Skeet [C# MVP]]

My second attempt: the -1 and 1 return values are the wrong way round
so the sort ends up recreating the the array indefinitely

Nope - if you return them one way round it tries to keep "fixed" at the
start of the list, and the other way round it tries to keep "fixed" at
the end of the list.

Jon

 

[Bill Butler]

I'm not sure whether I'd classify it as a bug in 1.1. Hint: if you give
2.0 different data (still just strings) but the same comparison method
you can break that, too - although it throws an exception rather than
hanging.

I know why it hangs in 1.1. (keeping quiet for the moment)
I don't know why in wouldn't hang in 2.0
Perhaps quicksort algorithm in 2.0 has been tweaked to avoid the terminal flaw????

Bill

 

[Chris S.]

my knowledge of quicksort and sorting algorithms isn't accomplished
enough to work it out. Please reveal all!

 

[Jon Skeet [C# MVP]]

my knowledge of quicksort and sorting algorithms isn't accomplished
enough to work it out. Please reveal all!

Okay, another hint: the problem is in the comparator, and the fact that
quicksort is being used isn't really relevant. Look at what the
contract for IComparer, and think about different possibilities for
what might be passed as the parameters...

(Bill: the algorithm has been tweaked. I don't believe it was tweaked
specifically to get around this flaw, but it's the kind of flaw which
is quite data-sensitive; depending on the data given, 2.0 either
notices the problem or happens to get the result right.)

Jon

 

[Wiktor Zychla [C# MVP]]

(Bill: the algorithm has been tweaked. I don't believe it was tweaked

specifically to get around this flaw, but it's the kind of flaw which

I do not even believe that they were aware of that. Seems that the tweaked
version is by chance better in handling such inconsistent comparers but is a
little controversial for other reasons:

http://tinyurl.com/7qab5 (I had a short discussion on that with Ryan
Byington from the dev team and I hope that we could expect it to be tuned
someday)

Wiktor Zychla

 

[Larry Lard]

Okay, another hint: the problem is in the comparator, and the fact that
quicksort is being used isn't really relevant. Look at what the
contract for IComparer, and think about different possibilities for
what might be passed as the parameters...

Oh I know I know! I think...


rot13

Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"?
Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur
fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be
fbzrguvat yvxr gung.

/rot13

 

[Wiktor Zychla [C# MVP]]

rot13

Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"?
Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur
fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be
fbzrguvat yvxr gung.

/rot13

although you does not seem to be fluent in ancient gnomish yet ("fubhyq" is
an irregular verb and the "guvf" noun should not be used in such content),
your explanation is fine

Wiktor Zychla

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi,

Spot on. Nice idea to rot13, too - it hadn't even occurred to me
(despite having seen it similarly used before). Doh!

First time for me, luckily wikipedia clarified it:
http://en.wikipedia.org/wiki/ROT13


I have one question though, IIRC the pivot should not be included in either
list when you divide your starting list. This is to avoid comparing a value
to itself (which is the cause of the problem in the particular example) ,
would it be that the quicksort argorithm has a bug after all?

Of course that even with a correct QS in place you may have errors, but only
when you have two "fixed" elements in the list, with one it should not be a
problem

Am I correct in the above?

It's early in the morning and I have had no coffe yet
I may be missing something

 

[Jon Skeet [C# MVP]]

Oh I know I know! I think...

rot13

Jung unccraf vs Pbzcner vf pnyyrq jvgu k naq l OBGU rdhny gb "svkrq"?
Gur erghea inyhr fubhyq or mreb va guvf pnfr ohg vg ergheaf -1, fb gur
fbeg vf crecrghnyyl gelvat gb fbeg svkrq gb gur yrsg bs vgfrys, be
fbzrguvat yvxr gung.

/rot13

Spot on. Nice idea to rot13, too - it hadn't even occurred to me
(despite having seen it similarly used before). Doh!

Jon

 

[Chris S.]

Yes, makes sense now.

 

[Bill Butler]

(Bill: the algorithm has been tweaked. I don't believe it was tweaked
specifically to get around this flaw, but it's the kind of flaw which
is quite data-sensitive; depending on the data given, 2.0 either
notices the problem or happens to get the result right.)

I don't mean that the algorithm was tweaked to fix this problem, but rather a slight optimization
accidentally fixed a broken IComparer. Similar to the standard C++ idiom to prevent self assignment.
I can explain what I mean more fully, but I am still being semi-cryptic.

Bill