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

[Ajuda] Merge Sort (recursivo) em C

Discussão em 'Programação' iniciada por c1t1z3n, 27 de Março de 2008. (Respostas: 7; Visualizações: 3852)

  1. c1t1z3n

    c1t1z3n Power Member

    boas..

    Tenho de fazer (entre outros) um algoritmo do mergesort em C, recursivo, e sem recorrer a um vector auxiliar... correria tudo sobre rodas não fosse o "sem recorrer a um vector auxiliar"..

    ja andei por googles, wikis e afins, mas nao consegui nada que me ajudasse a perceber como o fazer... qualquer ajuda ou dica é bem vinda =)

    thanks
     
  2. napalm

    napalm Power Member

    Em Python. Suponho que o ol que uso no código seja o tal vector auxiliar?
    Se sim, é possível tornar aquilo numa comparação recursiva entre listas mas não é bonito de se ver.

    Código:
    def mergesort(l):
      if len(l) == 1:
        return l
    
      half = len(l)/2
      l1 = mergesort(l[0:half])
      l2 = mergesort(l[half:])
    
      ol = []
      while True:
        if l1[0] > l2[0]:
          al, ul = l2, l1
        else:
          al, ul = l1, l2
                    
        ol.append(al.pop(0))
        if len(al) == 0:
          ol.extend(ul)
          break
      return ol
    
     
  3. c1t1z3n

    c1t1z3n Power Member

    antes de mais thx pela resposta... eu de python nao percebo nada :P .. mas à primeira vista parece de facto ter um vector auxiliar..

    mais alguem com ideias..?
     
  4. napalm

    napalm Power Member

    Logo à noite dou mais um tempito para pensar nisso, mas vai pensando como podes fazer um algoritmo recursivo que compare duas listas ordenadas e gere uma nova também ordenada. (ou seja a parte do meu código a partir do ol=[])

    Eg:

    [2,6] [3,8,10] => [2,3,6,8,10]

    Se resolveres este "pedaço" do problema tens o teu resolvido. Bom trabalho ;)
     
    Última edição: 27 de Março de 2008
  5. Ace-_Ventura

    Ace-_Ventura Power Member

    mergesort em C sem vector auxiliar? Em arrays não estou a ver como, em listas é possível:
    Código:
    struct layer_s *list_merge(struct layer_s *a, struct layer_s *b)
    {
    	struct layer_s head;
    	struct layer_s *c = &head;
    	while (a && b)
    	{
    		if (a->number < b->number)
    		{
    			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 layer_s *mergeSortList(struct layer_s *c)
    {
    	struct layer_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));
    }
     
  6. napalm

    napalm Power Member

    parte 2

    agora sem vector auxiliar:

    Código:
    def mergesort(l):
      if len(l) == 1:
        return l
    
      half = len(l)/2
      l1 = mergesort(l[0:half])
      l2 = mergesort(l[half:])
    
      return join(l1,l2)
    
    def join(l1, l2):
        if len(l1) == 0 or len(l2) == 0:
                l1.extend(l2)
                return l1
        if l2[0] > l1[0]:
                al = l1
        else:
                al = l2
        l = [al.pop(0)]
        l.extend(join(l1,l2))
        return l
    
    O código é mto simples e inteiramente recursivo. É uma questão de agora o passares para C.
     
  7. XpiritO

    XpiritO Power Member

  8. c1t1z3n

    c1t1z3n Power Member

    boas,

    obrigado a todos!.. dicas, codigo e tudo :D
    amanha volto a pegar no trabalho, que hoje é noite academica :banana:
     

Partilhar esta Página