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.Collecti ons;

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.WriteLi ne( s );

Console.WriteLi ne();
test.Sort( new TestComparer() );

foreach ( string s in test )
Console.WriteLi ne( s );
}
}

[Jon Skeet [C# MVP]]

Wiktor Zychla [C# MVP] wrote:

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]]

Wiktor Zychla [C# MVP] wrote:

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 ;)

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]]

Chris S. wrote:

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]]

Chris S. wrote:

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]

"Jon Skeet [C# MVP]" <sk***@pobox.co m> wrote in message
news:11******** *************@g 49g2000cwa.goog legroups.com...

Chris S. wrote:

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.

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