[Ajuda] Merge Sort (recursivo) em C

[c1t1z3n]

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

 

[napalm]

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.

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

 

[c1t1z3n]

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

mais alguem com ideias..?

 

[napalm]

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

 

[Ace-_Ventura]

mergesort em C sem vector auxiliar? Em arrays não estou a ver como, em listas é possível:

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));
}

 

[napalm]

parte 2

agora sem vector auxiliar:

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.

 

[XpiritO]

Tens aqui uma implementação em Java que dei na disciplinas de Algoritmos e Estruturas de Dados na universidade: http://www.deetc.isel.ipl.pt/Programacao/aed/turmas/LI31D/Code/SortingAlgorithms/MergeSort.java

 

[c1t1z3n]

boas,

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