By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,566 Members | 1,719 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,566 IT Pros & Developers. It's quick & easy.

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

P: n/a
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 );
}
}

Jan 26 '06 #1
Share this Question
Share on Google+
18 Replies


P: n/a
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

Jan 26 '06 #2

P: n/a
> 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

Jan 26 '06 #3

P: n/a
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

Jan 26 '06 #4

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

Jan 26 '06 #5

P: n/a
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

Jan 26 '06 #6

P: n/a
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
Jan 26 '06 #7

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

Jan 26 '06 #8

P: n/a
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

Jan 26 '06 #9

P: n/a
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:11*********************@g49g2000cwa.googlegro ups.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
Jan 27 '06 #10

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

Jan 27 '06 #11

P: n/a
Chris S. wrote:
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

Jan 27 '06 #12

P: n/a
> (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

Jan 27 '06 #13

P: n/a

Jon Skeet [C# MVP] wrote:
Chris S. wrote:
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...


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

--
Larry Lard
Replies to group please

Jan 27 '06 #14

P: n/a
> 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

Jan 27 '06 #15

P: n/a
Larry Lard wrote:
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

Jan 27 '06 #16

P: n/a
Yes, makes sense now.

Jan 27 '06 #17

P: n/a
Hi,
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:11**********************@g49g2000cwa.googlegr oups.com...
Larry Lard wrote:
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!


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

--
Ignacio Machin,
ignacio.machin AT dot.state.fl.us
Florida Department Of Transportation
Jan 27 '06 #18

P: n/a
"Jon Skeet [C# MVP]" <sk***@pobox.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...
(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
Jan 28 '06 #19

This discussion thread is closed

Replies have been disabled for this discussion.