1.09.2006

Sort a linked list

This is not an efficient way to sort a linked list (runs in O(N2), but it works when you don't care about efficiency (sometimes homework for a class). This code sorts a linked list in place with bubble sort.


do {
num_swaps = 0;
cur = q->head;
while (cur) {
if (cur->next) {
res = queue_element_compare(cur->e, cur->next->e);
if (res == 1) {
temp = cur->e;
cur->e = cur->next->e;
cur->next->e = temp;
num_swaps++;
}
}
cur = cur->next;
}
} while (num_swaps > 0);


queue_element_compare returns 0 on equal, 1 if e1 > e2 and -1 when e1 < e2.

0 Comments:

Post a Comment

<< Home