Tri d'un tableau - Page 2

Le tri par fusion prend bien plus de mémoire en temps d'exécution que les autres techniques.

pyroangel > t'es sur que ton algo (post 11) marche ?
J'ai essayé de le tester mais y'a des problèmes :
tableau_1 et tableau_2 ne sont pas initialisés !
et puis t'as pas détaillé la fonction fusionner.

>Kevin: Parce qu'il ne save pas l'implementer de maniere correcte. Bien implementer il ne prend rien comme memoire, et ne consomme que 10 instructions assembleurs par etape de tri !

jcop > dsl, ct juste pour donner une idée du fonctionnement, je vais te détailler l'initialisation des tableaux (il me semble qd même l'avoir fait), et la fusion...

>PpHd:
>>Kevin: Parce qu'il ne save pas l'implementer de maniere correcte. Bien implementer il ne prend rien comme memoire, et ne consomme que 10 instructions assembleurs par etape de tri !

Et on peut la voir cette implémentation?

int* Fonction Trier(int tableau[], int NbrElements)
{

if(NbrElements == 2)
{
if(tableau[0] > tableau[1])
{
int temp = tableau[0];
tableau[0] = tableau[1];
tableau[1] = temp;
}
return tableau;
}

int Milieu = NbrElements/2;
int tableau_1[max_qte/2];
int tableau_2[max_qte/2];

for (int i=0; i<Milieu; i++)
{
tableau_1[i] = tableau[i];
}
for (int i=0; i<Milieu; i++)
{
tableau_2[i] = tableau[Milieu+i];
}
// Les tableaux 1 et 2 sont initialisés maintenant

tableau_1 = Trier(tableau_1, Milieu);
tableau_2 = Trier(tableau_1, Milieu);

// fusion
int index = 0;
int i1 = 0;
int i2 = 0;

while(index < NbrElements)
{
if(tableau_1[i1] < tableau2[i2])
{
tableau[index] = tableau_1[i1];
i1++;
}
else
{
tableau[index] = tableau_1[i1];
i1++;
}
index++;
}
return tableau;
}

ok merci, je vais tester ça

Je ne l'ai pas sous la main. Mais c'est celle de genalib.

pyroangel > y'a encore un pb dans ton algo
où est définie la variable max_qte ?
et puis quand on déclare un tableau : faut mettre une constante (ou alors on l'alloue dynamiquement)

c pas des pb !!!

allez :
#define max_qte 40000 //Nombre pair qui définit le nbre max d'éléments que la fonction peut trier.

int tableau_1[max_qte/2];
int tableau_2[max_qte/2];

'max_qte/2) = constante, c comme int tablo[1000];
dc c alloué dans la pile

PS : Il vaudrait mieux allouer dynamiquement juste la taille nécessaire (Milieu) plutôt que d'utiliser max_qte éléments à chaque appel récursif.
Si tu veux que je te l'écrive avec l'allocation dynamique pour + avoir qu'à le recopier, dis-le moi...

(parce que là il sera pas super léger en RAM...)

si tu déclares un tableau statique, tu ne peux pas modifier sa valeur :
donc :
int tableau_1[max_qte/2];
...
tableau_1 = Trier(tableau_1, Milieu); // Erreur !

Par ailleurs y'a encore pleins d'erreurs dans ton code !!
Et je doute que tu l'aies fait marcher un jour.

Mais...
j'ai corrigé ton code (c'était pas facile), et maintenant ça marche bien !
voilà la solution :

#include <stdio.h>
#include <stdlib.h>

#define N 15
int tab[N] = { 455, 12, 899, 956, 750, 250, 5000, 5, 2, 50, 45, 789, 1564, 3, 19 };


int *Trier(int tableau[], int NbrElements)
{
int Milieu = NbrElements/2;
int *tableau_1;
int *tableau_2;
int index = 0;
int i1 = 0;
int i2 = 0;
int i;

if (NbrElements == 1)
return tableau;

if (NbrElements == 2) {
if (tableau[0] > tableau[1]) {
int temp = tableau[0];
tableau[0] = tableau[1];
tableau[1] = temp;
}
return tableau;
}
tableau_1 = (int *)malloc(Milieu*sizeof(int));
tableau_2 = (int *)malloc((NbrElements-Milieu)*sizeof(int));
for (i=0; i<Milieu; i++)
tableau_1[i] = tableau[i];
for (i=0; i<NbrElements-Milieu; i++)
tableau_2[i] = tableau[Milieu+i];
// Les tableaux 1 et 2 sont initialisés maintenant

tableau_1 = Trier(tableau_1, Milieu);
tableau_2 = Trier(tableau_2, NbrElements-Milieu);

// fusion

while(index < NbrElements) {
if((i1<Milieu && tableau_1[i1] < tableau_2[i2]) || i2== NbrElements - Milieu ) {
tableau[index] = tableau_1[i1];
i1++;
}
else {
tableau[index] = tableau_2[i2];
i2++;
}
index++;
}
free(tableau_1);
free(tableau_2);
return tableau;
}

void main(void)
{
int i;
for(i=0; i< N; i++)
printf("%d%c", tab[i], i==N-1?'n': ' ');
Trier(tab, N);
for(i=0; i< N; i++)
printf("%d%c", tab[i], i==N-1?'n': ' ');
}

j'ai une version différente du tri rapide, qui est plus rapide je pense. Je vais tester ça !
[edit]Edité par jcop le 06-04-2002 à 11:27:13[/edit]

en fait il s'agit du tri par fusion et non du tri rapide !
et puis l'algo ci-dessus doit pouvoir être amélioré.
je l'ai testé sur mon P2-300Mhz sur un tableau de 20000 nombres compris entre 0 et 32767 : le tri a pris env. 160-200 ms
mais c'est moins rapide que le tri rapide (en général) : j'ai testé le tri rapide sur ce même tableau, et le tri a pris env. 30-45 ms.

En gros c'est le tri rapide qu'il faut choisir, même pour des tableaux de petite taille (>5)
y'a l'algo ici :
http://perso.club-internet.fr/alainrey/algorithmes/quick.html
y'a aussi cet algo légèrement différent qui marche : (celui que j'ai utilisé)

void Trier(int tab[], int premier, int dernier)
{
    int temp, vmin, vmax, separateur;

    vmin = premier;
    vmax = dernier;
    separateur = tab[(premier + dernier)/2];
    do {
        while (tab[vmin] < separateur)
            vmin++;
        while (tab[vmax] > separateur)
            vmax--;
        if (vmin<=vmax) {
            temp = tab[vmin];
            tab[vmin++] = tab[vmax];
            tab[vmax--] = temp;
        }
    } while (vmin <= vmax);
    if ((premier < dernier-1)) {
        Trier(tab, premier, vmax);
        Trier(tab, vmin, dernier);
    }
}

on peut aussi tester différents tris à cette adresse : http://lwh.free.fr/pages/algo/tri/tri.htm

As-tu aussi essayé le ShellSort (celui qu'utilise qsort de TIGCCLIB)?

bah en fait je ne programme plus sur TI ...

Quelqu'un qui connait pourra peut-être me répondre?

Si on programme dans un langage fonctionnel, style Scheme ou Caml, le tri fusion est pas plus rapide en le faisant récursivement ???
J'ai essayé plusieurs méthodes, ça m'a semblé être le pluq rapide.

ca dépend de ce que tu as a trier ...

Mettons une liste de réels ou d'entiers

enfait, je crois que ca dépend surtout si la liste est presque triée ou pas

>jcop: bah en fait je ne programme plus sur TI ...

N'empêche que tu peux refiare ta comparaison en incluant le ShellSort, de façon à ce qu'on voie où il se situe par rapport à QuickSort et le tri par fusion.

Ton implementation du tri fusion est pas top

Oui, c'est le genre d'implémentations auquelles se référaient mes remarques comme quoi c'était lent et prenait beaucoup de mémoire en temps d'exécution.

Essayez d'implementez le tri fusion avec des listes. Juste comme ca.

Comme ceci?


let rec distribue l =
match l with
[] -> ([],[])
| x::[] -> (x::[],[])
| x::y::q -> let (l1,l2) = (distribue q) in (x::l1,y::l2)
;;

let rec fusion l1 l2 =
match l1,l2 with
[],_ -> l2
| _,[] -> l1
| t1::q1,t2::q2 -> if t1 < t2 then t1:fusion q1 l2)
else t2:fusion l1 q2)
;;

let rec tri_fusion l =
match l with
[] -> []
| x::[] -> x::[]
| _ -> let (l1,l2) = distribue l in fusion (tri_fusion l1) (tri_fusion l2)
;;


c'est trop joli le Caml, presque aussi bien que du Vian!

Le tri fusion, on peut le faire sur place, donc ça va...