PROGRAMME DE TRI

Commentaire de BlackGoddess le 14/07/2004 18:49:29

int tab [2][d]; >> tu compiles avec quel compilateur ?

normalement la taille d'un tableau DOIT être résolue a la compilation, hors la il est impossible de la connaître, puisque d est une saisie utilisateur (a l'execution donc).

Commentaire de BruNews le 14/07/2004 19:02:13 administrateur CS

Comme on te l'a fait remarquer plus haut, ton code ne compiler jamais. Faut une alloc dynamique.
Rectif attendue, merci.

BruNews, Admin CS, MVP Visual C++

Commentaire de Cyberboy2054 le 14/07/2004 21:54:42

C' est plutôt bon comme resultat. Mon implementation de quicksort, bien qu' étant simpliste et recursive, met 10 fois plus de temps dans les memes conditions.
Est il possible de dérécursifier quicksort, ou y-a-t' il des moyens de l'optimiser (genre une methode rapide pour trouver un bon pivot) ?

Commentaire de Maegis le 14/07/2004 23:27:52

>>>Cyberboy  
Il ne faut pas faire la comparaison avec un quicksort, ici tu as plein d'indications supplementaires dont le fait que les nombres sont tous positifs et plus petits que d
La donnée de d permet d'optimiser la fonction de tri
Les algos de quicksort, de heapsort ou de tri fusion sont optimum pour la seule donnée de la taille du tableau et le tableau lui-même. Avec des indications supplementaires on peut faire beaucoup mieux et on peut avoir des tris linéaires (en O(n)) plutôt que des quasi-linéaires (en O(n*ln(n)) )

>>>>>ekinoks
Ta fonction ne trie pas le tableau, si on décide de ne pas afficher les valeurs ton prog ne fait aucune opération sur tab2
Si on affiche les results, tu les affiches et c'est tout, à la fin le tableau tab 2 n'est pas trié

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

int main(int argc, char *argv[])
{
    DWORD deb, fin;
    int i,j,k;
int* tmp;
int nbchiffres;
int max;
int *tab,*tab2;
    printf("Nombre de chiffres a classer ?");
    scanf("%i", &nbchiffres);
    printf("Nombres allant de 0 a ?");
    scanf("%i", &max);

//alloc
tab = new int[nbchiffres];
tab2 = new int[max];

    for (i=0;i<nbchiffres;i++)       //Inscrit des nombres aleatoirement
tab[i]=(rand()%max);

   ZeroMemory(tab2,max); //on init tout a zero

deb = GetTickCount();
for (i=0;i<nbchiffres;i++)
tab2[tab[i]]++; //on compte le nb de fois que chaque nombre apparait

tmp = tab; //on sauve le pointeur
for (i=0;i<max;i++) //on recompose le tableau
{
k = tab2[i];
for (j=0;j<k;j++)
{
*tab=i;
tab++;
}
}
tab = tmp; //on restaure

    fin = GetTickCount();                   //fin du crono
    printf("Le tri a mis %d Ms\n", fin - deb);

delete[] tab;
delete[] tab2;
system("pause");

    return 0;
}
voila cette fonction trie un tab de 1.000.000 , 1.000.000 en 30ms chez moi et le qsort de la stdlib met 60ms


>>>>>BruNews
Le quicksort est forcement recursif !!!!
Il applique la méthode diviser pour regner :
On coupe le tableau en 2 selon le pivot (1ere moitié contenant les cases plus petites que le pivot, 2eme moitié le reste) et on appelle recursivement le programme sur les deux morceaux de tableau ainsi obtenus
C'est du recursif pur, qui dit diviser pour regner dit recursif.
Quoi qu'il en soit le quicksort est un bon algo dans la moyenne ( O(N*ln(N) ) bien que dans le pire des cas on atteigne une complexité en O(N^2)
Sinon il y a toujours le tri par tas (heapsort) qui est toujours en O (N*ln(N))

Commentaire de BruNews le 14/07/2004 23:41:53 administrateur CS

Robert Sedgewick explique la suppression de la recursivite (comme dit plus haut) a partir de la page 128 de: "Algorithmes en langage C".

Commentaire de djl le 15/07/2004 00:03:25

j'ai repris le meme algo de la methode sort() de ma classe matrice

Commentaire de BruNews le 15/07/2004 00:15:44 administrateur CS

http://www.cppfrance.com/code.aspx?ID=11151
c'est exemple ou j'ai devie le qsort de la CRT pour tout faire en interne. Juste que la il trie plus qu'un simple tableau de int, on peut donc beaucoup reduire le code de tri.

Commentaire de BruNews le 15/07/2004 00:25:42 administrateur CS

on est bien d'accord !!!

Commentaire de BruNews le 15/07/2004 12:35:56 administrateur CS

Je n'irais pas jusque la (encore que...) mais faut surtout plusieurs sources d'informations. Je te conseille Robert Sedgewick qui est une reference absolue.