Sorting IList<T> *in place*

  • Thread starter Thread starter Marcel Müller
  • Start date Start date
M

Marcel Müller

Is there a way to sort an IList<T> in place?

The solutions I found imply that you copy the current list to List<T>,
sort it and throw away the current IList<T> by replacing the reference
with a new list.

But this might be a very bad Idea if the IList<T> have been something
else than a simple List<T> before. Furthermore it requires by reference
access to the list parameter.

OK, I could copy the list, sort it, clear the original list and copy the
sorted content back to the original list. Seriously?

Isn't there any generic sort algorithm that can be applied to a generic
interface?


Marcel
 
Is there a way to sort an IList<T> in place?

The solutions I found imply that you copy the current list to List<T>,
sort it and throw away the current IList<T> by replacing the reference
with a new list.

But this might be a very bad Idea if the IList<T> have been something
else than a simple List<T> before. Furthermore it requires by reference
access to the list parameter.

OK, I could copy the list, sort it, clear the original list and copy the
sorted content back to the original list. Seriously?

Isn't there any generic sort algorithm that can be applied to a generic
interface?
Click to expand...

I would be skeptical about its usage, because IList does only
guarantee that elements can be accessed by index not that such
access will be efficient, so if access by index is O(n) instead
of O(1) performance will be very bad.

But a quicksort of IList<T> is easy to write.

Simple version:

public class QS
{
private static void SortHelp<T>(int n1, int n2, IList<T> lst)
where T : IComparable<T>
{
int l = n1;
int r = n2;
T pivot = lst[(n1 + n2) / 2];
do
{
while (lst[l].CompareTo(pivot) < 0) l++;
while (lst[r].CompareTo(pivot) > 0) r--;
if (l <= r)
{
T tmp = lst[l];
lst[l] = lst[r];
lst[r] = tmp;
l++;
r--;
}
} while (l <= r);
if (n1 < r) SortHelp(n1, r, lst);
if (l < n2) SortHelp(l, n2, lst);
return;
}
public static void Sort<T>(IList<T> lst) where T : IComparable<T>
{
SortHelp(0, lst.Count - 1, lst);
}
}

Arne
 
Sure, as long as it's not a read-only IList<T>. Of course there is.

Now, there's nothing in .NET that I know of that will do that. The built-in
sort implementations apply to arrays or List<T> instances. But there's
nothing stopping you from writing your own.
Click to expand...

Oh, that's the point that I wanted to avoid.
It's unbelievable that business applications that use a modern
development environment need to ship with their own general purpose sort
algorithmn, isn't it?.

You should use your favorite web search engine to look for a third-party
library that does that. Even if it doesn't support IList<T> directly, with
an open-source library it would be easy enough to port the existing
algorithm to do so.
Click to expand...

I have implemented quicksort several time on several platforms. But most
times I had old environments like REXX or C.

http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Heapsort

Those are two of the best general-purpose sorts, both of which can be
implemented to be both memory- and time-efficient.
Click to expand...

I know.


Marcel
 
Oh, that's the point that I wanted to avoid.
It's unbelievable that business applications that use a modern
development environment need to ship with their own general purpose sort
algorithmn, isn't it?.
Click to expand...

No.

You don't want to create a sort method that may perform very
poorly depending on the IList implementation.

You want to create a sort method for something where you know
access via index is fast and then developers can convert as
mentioned in original post.

Arne
 
No.

You don't want to create a sort method that may perform very
poorly depending on the IList implementation.

You want to create a sort method for something where you know
access via index is fast and then developers can convert as
mentioned in original post.
Click to expand...

Java Collections.sort sort List<T> which is the interface
in Java.

But note what they write in the docs:

<quote>
This algorithm offers guaranteed n log(n) performance. This
implementation dumps the specified list into an array, sorts the array,
and iterates over the list resetting each element from the corresponding
position in the array. This avoids the n2 log(n) performance that would
result from attempting to sort a linked list in place.
</quote>

Arne
 
You don't want to create a sort method that may perform very
poorly depending on the IList implementation.
Click to expand...

Hmm, in C++ STL it is best practice not to expose interfaces that cannot
be implemented reasonably fast. Consequently linked lists do not provide
direct access.

Most of the time .NET follows this rule too. I.e. properties (like Item)
should be O(1) or at most O(log(n)). AFAIK there is no .NET container
that implements IList<> with O(n) member access.

Looking back 20 years, I also prefer this rule, since programmers tend
not to look at the performance of each function that they call in a
loop. I had hundreds of sessions where I had to remove code like that
because it was incredibly slow or it used (shared) system resources
excessively.

From that point of view, LINQ is a pain. While I personally like the
expressive syntax, performance problems have become much more common
with LINQ. Entire sub expressions are evaluated over and over
accidentally. LINQ does not fit very well into non-functional languages.
But there are still many advantages too.


Marcel
 
Hmm, in C++ STL it is best practice not to expose interfaces that cannot
be implemented reasonably fast. Consequently linked lists do not provide
direct access.
Click to expand...

..NET LinkedList said:
Most of the time .NET follows this rule too. I.e. properties (like Item)
should be O(1) or at most O(log(n)). AFAIK there is no .NET container
that implements IList<> with O(n) member access.
Click to expand...

I do not even remember anything besides the array backed List<T> that
implements IList<T>.

But I assume that the original poster must have some class in
mind otherwise the problem would not exist.

And the most likely reason for the existence of such a class
must be that for whatever reason array backed it not possible.
From that point of view, LINQ is a pain. While I personally like the
expressive syntax, performance problems have become much more common
with LINQ. Entire sub expressions are evaluated over and over
accidentally. LINQ does not fit very well into non-functional languages.
But there are still many advantages too.
Click to expand...

Classic tradeoff.

I have noted the effect as well.

But for small data sizes and modern hardware it does not matter.

Arne
 
I do not even remember anything besides the array backed List<T> that
implements IList<T>.
Click to expand...

Hmm, seems you are right. And the implicit conversion from T[] to
IList said:
But I assume that the original poster must have some class in
mind otherwise the problem would not exist.
Click to expand...

No, I prefer IList<T> in public interfaces because it offers the
implementer the option to use T[] for long lived or constant size arrays
and List<T> for arrays that are subject to change. Furthermore I can
replace IList<T> with a read-only proxy in debug builds to ensure
constness in some places where anything else would result in hard to
find race-conditions. Of course, not in this case.


Marcel
 
I do not even remember anything besides the array backed List<T> that
implements IList<T>.
Click to expand...

Hmm, seems you are right. And the implicit conversion from T[] to
IList said:
But I assume that the original poster must have some class in
mind otherwise the problem would not exist.
Click to expand...

No, I prefer IList<T> in public interfaces because it offers the
implementer the option to use T[] for long lived or constant size arrays
and List<T> for arrays that are subject to change. Furthermore I can
replace IList<T> with a read-only proxy in debug builds to ensure
constness in some places where anything else would result in hard to
find race-conditions. Of course, not in this case.
Click to expand...

I would make it readonly in all build for those cases.

Allowing caller code to access the data directly is
breaking encapsulation.

If a sort is needed then the class should have a sort
method that could sort the implementation.

But OK I have no guarantee that the original poster sees
it that way, so I see your point.

Arne
 
.NET does already include at least two different sorting APIs (not even
counting "order by" in LINQ, and other corner cases).

You have a specific requirement that is more constraining that what .NET
offers. But you haven't explained the requirement, and it's unusual enough
that it's not surprising that you might have to "roll your own". For most
applications, the difference between O(n log n) and O(n (log n + 2)) is
insignificant, especially given how incredibly fast sequential memory
copies are on modern hardware.
Click to expand...

Strictly speaking there are no difference between O(n log n)
and O(n (log n + 2)) at all.

Not that it really matters for your argument, which I agree with.

Arne
 
Back
Top