Olá!
Alguém sabe onde consigo arranjar um algoritmo para ordenar listas ligadas por um determinado campo?
Só consigo algoritmos que ordenam enquanto estou a inserir. :'(
Obrigada desde já!

tenta arranjar um qsort....

com apontadores isso deve ser bem lixado...

tenta arranjar um qsort....

com apontadores isso deve ser bem lixado...

Pois... Normalmente esses algoritmos existem para vectores não para listas ligadas. :(

usa o mergesort. É o melhor algoritmo de ordenação baseado em comparações para listas.

int compare(struct list_s *a, struct list_s *b)
{
if(a->item < b->item) return 1;

return 0;
}


struct list_s *list_merge(struct list_s *a, struct list_s *b)
{
struct list_s head;
struct list_s *c = &head;
while (a && b)
{
if (compare(a,b))
{
c->next = a;
c = a; a = a->next;
}
else
{
c->next = b;
c = b; b = b->next;
}
}
c->next = (!a) ? b : a;
return head.next;
}

struct list_s *mergeSortList(struct list_s *c)
{
struct list_s *a, *b;
if (!c || !c->next)
{
return c;
}
a = c;
b = c->next;
while (b && b->next)
{
c = c->next;
b = b->next->next;
}
b = c->next;
c->next = NULL;
return list_merge(mergeSortList(a), mergeSortList(b));
}

Acordei a pensar no teu problema, e uma vez que já sabes criar uma pista ordenada, o mais fácil é criares uma segunda lista ordenada da forma que quiseres, sem mexer na lista original :)

podes usar o quicksort e em vez de trocar os indices como fazias no vector trocas o ponteiro do elemento seguinte, claro que seria mais facil se fosse uma lista duplamente ligada em que tens ponteiro para o item anterior e seguinte

Ou criar um array de ponteiros, onde um índice do array corresponde a um elemento da lista, e utilizar o qsort nesse array.

Cumps,
JP

ou então usa o mergesort que eu meti ai, que faz é O(nlogn) tal como o qsort..

Olá, sim concordo que a tua solução é a mais adequada e mais simples de implementar :)

Só tinha falado no quicksort, por uma questão de escolha e para dar a ideia que também podemos adaptar o qsort a listas simplesmente ligadas, de um modo relativamente simples.

Penso que uma motivação válida para utilizar o quicksort que, em certos casos patológicos, pode até ter uma complexidade assimptótica superior ao merge sort: O(n^2), são as optimizações que têm sido feitas ao longo das várias versões da libc, que se podem traduzir em alguns ganhos de performance: (http://www.cs.sunysb.edu/%7Eskiena/214/lectures/lect17/lect17.html)

"...When Quicksort is implemented well, it is typically 2-3 times faster than mergesort or heapsort. The primary reason is that the operations in the innermost loop are simpler. The best way to see this is to implement both and experiment with different inputs..."

Cumps,
JP