sort a generic linked list?

  • Thread starter Thread starter Nick Valeontis
  • Start date Start date
N

Nick Valeontis

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 ?
 
I know how to use Icomparable.
However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)
Click to expand...

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
-----------------------------------------
 
Gaurav Vaish (www.edujini-labs.com) said:
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
Click to expand...

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.
 
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<ddd> a = new LinkedList<ddd>();
a.AddLast( ... a ddd ...);
a.AddLast( ... a ddd ...);
a.AddLast( ... a ddd ...);

SortedList<int, ddd> b = 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?
 
That is actually a good approach.
Click to expand...

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.
Click to expand...

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.
Click to expand...

True. Or, more properly, arrays sort well using a wider variety of
algorithms than do linked lists, because indexing into an array is
cheap.
 
Michael A. Covington said:
Linked lists are inherently not sortable without a lot of extra work
linking and unliking things. Arrays are very sortable.
Click to expand...

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
 
Back
Top