Tuesday, December 06, 2005

libyirae: simple sorting of singly linked lists

And so the story goes…

I have finally done it yippee!!! :-) Source will be available at http://datavibe.net/~essiene/downloads/yirae-0.2-tar.gz before the end of the day.

(needless to say, i built this on a GNU system, so gcc in any of its incarnations will work [cygwin, ming, etc]

After my last ungainly experience with those-pesky-lists™, I had to go follow most of the links I had bookmarked to see how guys have been tackling sorting of singly linked lists. Everyone seemed to agree that they were harder than sorting doubly linked lists (at least I have to believe that, so I don’t feel dumber than I’m feeling presently :)). Anyways, there are a number of approaches, but I’ll try to explain the one I like best.

First imagine you have a list like:


When traversing this list, and you come across 2, you just have to swap it with 3 and you’re done. Imagine instead that you have:


A single pass would go something like this:

You don’t touch 1, then you swap 3 and 2, you then swap 5 and 1 and you don’t touch 7… the result looks like:


Tada… its still not sorted, you’ll have to pass thru this list at least two more times, before you get the desired:


This raises a number of issues… 1st you have to repeat this process basically till you can verify that all your elements are in order… for a long list, this is just not acceptable. Anyways… this was the most obvious approach, and its ridden with a number of issues.

The other not so obvious approach is this. First, imagine that you have an InsertSorted() function that will insert an element such as to keep its place. It doesn’t sort an existing list, but it will not add to the confusion if its not sorted. So if I have:


And I call InsertSorted(2) on this list, it will result in:


Once I have a method like that, I can proceed to one of two implementations for the sorting:

Method 1 – the least brain tickling path
1. iterate thru the list
2. POP each node you meet, OFF the list (remember POP removes a node)
3. InsertSorted each node you POP into a new list
4. return the new list :)

Nice and easy, this is the current implementation I have. Though, I’ve been wondering about the cost of the new list in the whole process. Also, my current implementation has another Node memory overhead (I’ve explained that one in the code). There is a second method, that at first glance, seems more efficient, though after thinking thru it, the efficiency can just to tied down to the process of creating a new linked list that the first method incurs, if that cost can be shown to be zero, then there is basically no loss or gain as far as I can think, anyway, the second method goes thus:

Method 2 – using only one list
1. iterate thru the list
2. if you find any node out of sorted order, Unlink the Node (unlink doesn’t destroy the Node, just removes it from the list and returns the Node to you)
3. InsertSorted the node back into the list.
4. return the list

This method seems to be more efficient than the method 1, but I’ve not done any testing/profiling so I don’t know for sure. After thinking for a while, there is really no memory usage difference, as in the first case, when the new list grows as the old list decreases. Also, the creation of a new list isn’t a costly operation at all by my implementation.

If you look thru the code, you’ll see that my public functions deal with data not nodes, so I POP data, and I Insert data hence I always have to create an underlying Node object to help me out… I’m thinking of having utility versions of all these operations that pop Nodes and Insert Nodes, so I can reuse the memory without free’ing one only to allocate it later…

Anyways, the code is free to look at. I hope it helps some other person, especially if (s)he’s doing an assignment ;)

Oh finally, the thing that makes me happy is that ynode_test.c is totally valgrind approved :D, I hear LinkedLists are always a point where guys leak memory, but I guessed I closed mine up well… maybe not NewsWorthy™, but definitely something for me to be proud about.

Essien out!


Post a Comment

<< Home