pereges wrote:

>

.... snip ...

>

Is it easier to sort link lists as opposed to arrays ?? In one

implementation of quick sort applied on link lists, I saw that

even accessing a single Nth node required n-1 passes.

Sorting lists is easy, and O(NlogN). See the following code:

/* List handling, reversal, sort, merge, split */

/* file listops.c */

/* By C.B. Falconer. Public Domain, use as you wish */

/* Attribution appreciated. */

/* =============== === 30 April, 2001 =============== === */

#include "listops.h"

/* =============== =============== =============== ========== */

/* believed necessary and sufficient for NULL terminations */

/* Reverse a singly linked list. Reentrant (pure) code */

nodeptr revlist(nodeptr root)

{

nodeptr curr, nxt;

if (root) { /* non-empty list */

curr = root->next;

root->next = NULL; /* terminate new list */

while (curr) {

nxt = curr->next; /* save for walk */

curr->next = root; /* relink */

root = curr; /* save for next relink */

curr = nxt; /* walk onward */

}

}

/* else empty list is its own reverse; */

return root;

} /* revlist */

/* =============== =============== =============== ========== */

/* split list p into 2 nearly equal lists, return 2nd part */

nodeptr splitlist(nodep tr p)

{

nodeptr p1, p2, p3;

p1 = p2 = p3 = p;

if (not p) return NULL;

do {

p3 = p2;

p2 = p2->next; /* advance 1 */

p1 = p1->next;

if (p1) p1 = p1->next; /* advance 2 */

} while (p1);

/* now form new list after p2 */

p3->next = NULL; /* terminate 1st half */

return p2;

} /* splitlist */

/* =============== =============== == */

/* Merge two ordered lists into one */

nodeptr mergelists(node ptr p1, nodeptr p2,

int (*cmp)(void *, void*)) /* compare */

{

node n;

nodeptr p;

p = &n;

n.next = p;

while (p1 and p2) {

if (cmp(p1, p2) <= 0) {

p->next = p1; p = p1; p1 = p1->next;

}

else {

p->next = p2; p = p2; p2 = p2->next;

}

}

/* at least one list now empty, copy other */

/* one or both of these operations is null */

if (p1) p->next = p1;

if (p2) p->next = p2;

/* check for empty lists */

if (n.next == &n) return NULL;

return n.next;

} /* mergelists */

/* =============== =============== =============== ===== */

/* Recursively sort a linked list. The sort is stable */

/* This is an O(NlogN) process for all lists. */

nodeptr mergesort(nodep tr root,

int (*cmp)(void *, void*)) /* compare */

{

nodeptr p;

if (root and root->next) { /* 2 up items in list */

p = splitlist(root) ; /* alters list root */

root = mergelists(merg esort(root, cmp),

mergesort( p, cmp),

cmp);

}

/* else the unit or empty list is already sorted */

return root;

} /* mergesort */

/* end listops.c */

and the header file:

/* List handling, reversal, sort, merge, split */

/* file listops.h */

/* By C.B. Falconer. Public Domain, use as you wish */

/* Attribution appreciated. */

/* =============== === 30 April, 2001 =============== === */

#ifndef listops_h_

#define listops_h_

#include <stddef.h/* NULL */

#include <iso646.h/* not, and */

/* The bare minimum to form a linked list */

typedef struct node {

struct node *next;

void *data;

} node, *nodeptr;

/* =============== =============== =============== ========== */

/* believed necessary and sufficient for NULL terminations */

/* Reverse a singly linked list. Reentrant (pure) code */

nodeptr revlist(nodeptr root);

/* =============== =============== =============== ========== */

/* split list p into 2 nearly equal lists, return 2nd part */

nodeptr splitlist(nodep tr p);

/* =============== =============== == */

/* Merge two ordered lists into one */

nodeptr mergelists(node ptr p1, nodeptr p2,

int (*cmp)(void *, void*)); /* compare */

/* =============== =============== =============== ===== */

/* Recursively sort a linked list. The sort is stable */

/* This is an O(NlogN) process for all lists. */

nodeptr mergesort(nodep tr root,

int (*cmp)(void *, void*)); /* compare */

#endif

/* end listops.h */

--

[mail]: Chuck F (cbfalconer at maineline dot net)

[page]: <http://cbfalconer.home .att.net>

Try the download section.