1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Ordenar listas ligadas em C

Discussão em 'Programação' iniciada por Mitsuki, 16 de Junho de 2008. (Respostas: 8; Visualizações: 6611)

  1. 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á!
     
  2. antek

    antek Power Member

    tenta arranjar um qsort....

    com apontadores isso deve ser bem lixado...
     
  3. Pois... Normalmente esses algoritmos existem para vectores não para listas ligadas. :(
     
  4. Ace-_Ventura

    Ace-_Ventura Power Member

    usa o mergesort. É o melhor algoritmo de ordenação baseado em comparações para listas.
    Código:
    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));
    }
     
  5. antek

    antek Power Member

    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 :)
     
  6. Evil_Tidus

    Evil_Tidus Power Member

    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
     
  7. countzero

    countzero Power Member

    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
     
  8. Ace-_Ventura

    Ace-_Ventura Power Member

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

    countzero Power Member

    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:

    "...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
     

Partilhar esta Página