tri - Page 1

Salut,
voilà le pb j'ai deux tableaux triés et je veux en obtenir un autre trié qui resulte de l'insertion de l'un dans l'autre.
je me demandais s'il y avait plus rapide que le parcours des deux tableaux avec une comparaison à chaque fois pour trouver le plus petit et le copier dans le tableau resultat, puis d'incrementer l'indice du tableau qui a fournit la valeur. et on fait ca jusqu'a ce que les deux tableaux soient arrivés au bout.
merki

[google]merge sort[/google] ?

Ben, non, je vois pas comment il pourrait y avoir plus rapide... le seul truc c'est que quand tu as fini un tableau tu peux copier le reste de l'autre direct, éventuellement avec memcpy

Il n'y a pas plus rapide avec ces structures de données dans le pire des cas, mais peut-être que d'autres structures de données seraient plus appropriées à ton problème ?

Tu peux concaténer les 2 tableaux (de façon logique pour pas gspiller de la mémoire...) et utiliser un algo de tri conventionnel? (QuickSort, Tri par tas, Tri à bulle...).

geogeo > non mais là ses tableaux d'origine sont déjà triés, il veut juste les fusionner

[cross, je répondais à geogeo]
Ah oui, un algo en O(n*log n) ou O(n^2) va sûrement être plus rapide que son algo en O(n)

(je répète, on peut *prouver* que dans le pire des cas on est obligé de lire les deux tableaux, donc son algo est optimal dans le pire des cas à un facteur constant près)

Arf en effet, je suis HS, désolé.

Quelque chose comme ça ?

void lenomquivabien (int *tab1, int *tab2, int taille1, int taille2, int *res) {
	int i=0;
	int i1=1;
	int i2=1;
	int m1=tab1[0];
	int m2=tab2[0];
	while (i<taille1+taille2) {
		while (i1<=taille1 && (m1<=m2 || m2>taille2)) {
			res[i++]=m1;
			m1=tab1[i1++];
		}
		while (i2<=taille2 && (m2<=m1 || m1>taille1)) {
			res[i++]=m2;
			m2=tab2[i2++];
		}
	}
}

edit : #rien# pour faire plaisir à Thepro

L'implémentation du ./9 donnera un meilleur résultat pour fusionner deux tableaux du genre {1,2,3,4,5} et {6,7,8,9,10}, et celle du ./10 sera plus rapide sur des tableaux du genre {1,3,5,7,9} et {2,4,6,8,10}.
Non ?

Sally :
il faut initialiser i1 et i2 à 1

Effectivement ^^

un brin compliqué

Eh oui, le but n'était pas que ce soit simple (à cause de toi, LionelA n'a plus rien à faire )

Sasume :
L'implémentation du ./9 donnera un meilleur résultat pour fusionner deux tableaux

En fait les 2 codes sont les même avec moins de tests pour celui de Sally, il ne doit pas y avoir une grande différence.

Bah si c'est ça je veux bien effacer mon post (mais en fait je pense qu'il savait déjà comment faire, il demandait juste s'il y avait une meilleure méthode ^^)

mon code est en asm intel mais pour l'instant il segfaulte
je le mettrais demain qd je serais au boulot

Je ne sais pas si c'est bien de faire une lecture en dehors des tableaux

Je ne pense pas que ça puisse être gênant, mais c'est une bonne question

#8 > il est curieusement construit cet algo... et si taille1 = 0 ou taille2 = 0, ça accède à une zone mémoire interdite ?

Thepro :
Je ne sais pas si c'est bien de faire une lecture en dehors des tableaux

Non, en général c'est très très mal ^^ (sauf sur TI où ça ne fait rien, mais dès qu'il y a une MMU ça peut faire n'importe quoi, même si 90% du temps ça ne sera pas grave...)


Si on veut être efficace et stocker dans PC un maximum d'informations :

for (;; )
  if (m1<m2) {
    *r++ = m1;
    if (!n1--) {
      *r++ = m2;
      while (n2--)
        *r++ = *p2++;
      break;
    }
    m1 = *p1++;
  } else {
    *r++ = m2;
    if (!n2--) {
      *r++ = m1;
      while (n1--)
        *r++ = *p1++;
      break;
    }
    m2 = *p2++;
  }

ah c'est ça qu'il voulait dire ds le post #14...
(en même temps, tt ça c'est exactement l'algo naïf décrit par LionelA au 1er post, non ?)

Ben oui Mais cf ./4...

j'ai pas le code sous la main il est sur une autre machine mais en gros j'ai fait ce que vous avez dit avec la recopie a la fin mais bon au final c'est moins rapide que ce que j'avais deja fait (en fait c'etait un test d'une autre technique)
voila voila

Menfin bon si tu veux faire plus efficace tu seras obligé de te placer à un niveau plus global ^^ (i.e. qu'est-ce que tu vas faire avec les tableaux d'entrée et de sortie)

ben le pb c'est que j'ai pas le droit de détailler, c'est du confidentiel CNES