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

sort a generic linked list?

P: n/a
I know how to use Icomparable.

However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)

Lets say I have something like this:
class DisJunctiveConstraintList : LinkedList<DisjunctiveConstraint>

class DisjunctiveConstraint { public int Selection ... }
And i want to sort by Selection ?
--
With regards,

Nick
Jan 28 '07 #1
Share this Question
Share on Google+
6 Replies


P: n/a
>I know how to use Icomparable.
>
However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)
There's no way out using inbuilt API.
You'll need to write your own... or there's a way around:

1. Convert LinkedList into an array.
2. Sort the array
3. Convert the array back to LinkedList

:)
--
Happy Hacking,
Gaurav Vaish | www.mastergaurav.com
www.edujini-labs.com
http://eduzine.edujini-labs.com
-----------------------------------------
Jan 28 '07 #2

P: n/a

"Gaurav Vaish (www.edujini-labs.com)" <ga*****************@nospam.gmail.com>
wrote in message news:uz**************@TK2MSFTNGP04.phx.gbl...
I know how to use Icomparable.

However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)

There's no way out using inbuilt API.
You'll need to write your own... or there's a way around:

1. Convert LinkedList into an array.
2. Sort the array
3. Convert the array back to LinkedList
That is actually a good approach. Linked lists are inherently not sortable
without a lot of extra work linking and unliking things. Arrays are very
sortable.
Jan 28 '07 #3

P: n/a
Hmm,

Then, I guess I would have to write sth like this:

class ddd {
public int i;
public string name;
public ddd(int i, string name) {
this.i = i;
this.name = name;
}
(... implement Icomparable)
}

LinkedList<ddd a = new LinkedList<ddd >();
a.AddLast( ... a ddd ...);
a.AddLast(... a ddd ...);
a.AddLast(... a ddd ...);
List<ddd b = new List<ddd >();
foreach (ddd item in a) {
b.Add(item);
}
b.Sort();
a.Clear();
foreach (ddd item in b) {
a.AddLast(item);
}
or this:
class ddd {
public int i;
public string name;
public ddd(int i, string name) {
this.i = i;
this.name = name;
}
}

LinkedList<ddda = new LinkedList<ddd>();
a.AddLast( ... a ddd ...);
a.AddLast( ... a ddd ...);
a.AddLast( ... a ddd ...);

SortedList<int, dddb = new SortedList<int, ddd>();
foreach (ddd item in a)
b.Add(item.i, item);
a.Clear();

foreach (ddd item in b.Values)
a.AddLast(item);
foreach (ddd item in a)
Console.WriteLine(item.i + " " + item.name);

So, just wandering ... Is there a better way to make the conversion
LinkedList -List in order to sort it?

Are the two ways above equivalent?

The second way should require more memory, but perhaps is faster?
--
With regards,

Nick
"Michael A. Covington" <lo**@ai.uga.edu.for.addresswrote in message
news:u5**************@TK2MSFTNGP04.phx.gbl...
>
"Gaurav Vaish (www.edujini-labs.com)"
<ga*****************@nospam.gmail.comwrote in message
news:uz**************@TK2MSFTNGP04.phx.gbl...
>I know how to use Icomparable.

However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)

There's no way out using inbuilt API.
You'll need to write your own... or there's a way around:

1. Convert LinkedList into an array.
2. Sort the array
3. Convert the array back to LinkedList

That is actually a good approach. Linked lists are inherently not
sortable without a lot of extra work linking and unliking things. Arrays
are very sortable.


Jan 28 '07 #4

P: n/a
On Jan 28, 10:22 am, "Michael A. Covington"
<l...@ai.uga.edu.for.addresswrote:
"Gaurav Vaish (www.edujini-labs.com)" <gaurav.vaish.nos...@nospam.gmail.com>
wrote in messagenews:uz**************@TK2MSFTNGP04.phx.gbl. ..
>I know how to use Icomparable.
However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)
There's no way out using inbuilt API.
You'll need to write your own... or there's a way around:
1. Convert LinkedList into an array.
2. Sort the array
3. Convert the array back to LinkedList
That is actually a good approach.
Agreed. So long as the list isn't enormous (tens of thousands of
elements or more), the overhead of switching to an array and then back
again probably won't be too bad.
Linked lists are inherently not sortable without a lot of extra work linking and unliking things.
I disagree. I've written QuickSort for a linked list before and there
was no linking or unlinking involved. In fact, any basic exchange sort
works just great with a linked list. What costs big time is needing to
find a specific index in the list, because you have to search for it.
Most exchange sorts, however, move forward and backward through the
list, which is cheap. Exchanging elements becomes simply swapping
pointers or values, which is also cheap.
Arrays are very sortable.
True. Or, more properly, arrays sort well using a wider variety of
algorithms than do linked lists, because indexing into an array is
cheap.

Jan 28 '07 #5

P: n/a
Michael A. Covington <lo**@ai.uga.edu.for.addresswrote:

<snip>
That is actually a good approach. Linked lists are inherently not sortable
without a lot of extra work linking and unliking things. Arrays are very
sortable.
You need to use a different approach to sorting for a linked list, but
some sort algorithms work surprisingly well.

See
http://www.chiark.greenend.org.uk/~s.../listsort.html
for an example.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Jan 29 '07 #6

P: n/a
"Michael A. Covington" <lo**@ai.uga.edu.for.addresswrites:
Linked lists are inherently not sortable without a lot of extra work
linking and unliking things. Arrays are very sortable.
Well, as pointed out also by Jon Skeet, linked lists can be sorted
using mergesort in worst-case time O(n log n), without extra memory,
and stably (not changing the order of equal elements). In many
respects this provides better functionality than quicksort on arrays.

The C5 collection library for C#/.NET has such an sorting
implementation for linked lists; http://www.itu.dk/research/c5/

Peter
Jan 29 '07 #7

This discussion thread is closed

Replies have been disabled for this discussion.