Linked List Sorting

Sort while inserting in your list (needs double linked list), which works in linear time.

You could use a priority queue instead implemented by a heap which works in log n time.

I need to sort the list after it has been created.

Where is the problem with sorting while inserting ?

You are inserting anyway.

Enumerate into an array and quicksort.

O(n) + O(n log n) -> O(n log n)

thats only if you cant sort on insertion...

If you data is too big for copying into an array, then you are left with bubble sort. that O(n^2) which makes it potentially slower anyway, so you might as well copy it into an array assuming you have the memory.

Heapsort works in O(n log n) as well for an input size of n (quicksort having betters constants, i guess).
But WHY not sorting while inserting ?

You have to insert anyway.

What you do is:
1. create lili (which is inserting n elements)
2. create structure for sorting (array, p queue, whatever)
3. create (now sorted) lili again ?

???

well.. you can also sort a linked list after it has been created but to make life easier you got to make it doubly-linked [not mandatory though].

for example you have a structure like this one

typedef struct node{
// data
struct node *next;
struct node *prev;
}

and you have a linked list like this one.. pictorially

HEAD -> A <--> B <---> C <---> D <---> E <---> F <---> G --->NULL

where <---> represents a double-link [ the "next" and the "prev" ]
i hope u got the picture

now suppose you want to swap the content of the node B with the node F.

A.next = F;
F.prev = A;

C.prev = F;
F.next = C;

E.next = B;
B.prev = F;

G.prev = B;
B.next = G;

now the question is .. where do you get A, C, E and G from ?
simple....

A = B.prev;
C = B.next;

E = F.prev;
G = F.next;

This is why life gets simplier when you have a doubly linked list instead of "singly" [ i''m sure there''s nothing called singly though ] because you can traverse both ways, which is very crucial when you want to serious data manipulation with linked-list. As a matter of fact.. coding a doubly linked list is much easiar than coding a "singly" one when it comes to data manipulation.. trust me.

The example that i''ve shown was just a flow diagram drawn textually and that should be able to float your boat if you are a mature enough programmer.

Good Luck !

sorting on insertion isn''t linear on linked lsts, because finding the insertion point forces you to romp around alot, in the worst case it''s as bad as O(n^2)!

I''m always a fan of bottom-up MergeSort for linked lists, but for any one of these algorithms the only way you''ll find out how they work is if you STFW

George D. Filiotis

I am a signature virus. Please add me to your signature so that I may multiply.

This is all bollocks. Lists aren''t for post-insertion sorting. Either figure out how to do a sorted insert or make it a tree.

agreed


sort the data as you insert it...it keeps nice and neat that way

OK i have the following code but to sort a linked list but it never sorts the first element. Any ideas?

void SortLinkedList(int axis)
{
_RAY_TRACING_SYSTEM *rts = RayTracingSystem;

_OBJECT *last = NULL;
int exchange = TRUE;
int notfinsihed = TRUE;
_OBJECT *temp = rts->object_heap;

while(exchange)
{
_OBJECT *r, *p, *q, *newlast = NULL;

exchange = FALSE;
r = rts->object_heap;
p = r->next;
q = p->next;

while(q != NULL)
{
float p_val, q_val;

switch(axis)
{
case 0://X
p_val = GET_X(p->center_pos);
q_val = GET_X(q->center_pos);
break;
case 1://Y
p_val = GET_Y(p->center_pos);
q_val = GET_Y(q->center_pos);
break;
default:
p_val = GET_Z(p->center_pos);
q_val = GET_Z(q->center_pos);
break;
}

if(p_val > q_val)
{
_OBJECT *t;

r->next = q;
p->next = q->next;
q->next = p;

t = p;
p = q;
q = t;

newlast = q;
exchange = TRUE;
}

r = p;
p = q;
q = q->next;
}

last = newlast;
}
}

The format of this code is difficult to read....anyone tell me how to put it in a nice scroll box?

Use the two tags [ source ] and [ /source ] without the lil spaces I put there.




[edited by - blaste on April 22, 2003 7:06:58 PM]

Inserting into a presorted linked list is O(n). Assuming your program does all the inserting, sorting on insertion will be O(n).

Thanks for the code complexity concerns but speed isn''t really an issue in the sorting function.

OK it seems that no-one can fix the code i posted so how about has anyone got any that would do the same thing?