PROGRAMME DE TRI
BlackGoddess
Messages postés
338
Date d'inscription
jeudi 22 août 2002
Statut
Membre
Dernière intervention
14 juin 2005
-
14 juil. 2004 à 18:49
StanOfSky Messages postés 43 Date d'inscription mardi 30 mars 2004 Statut Membre Dernière intervention 7 octobre 2006 - 15 juil. 2004 à 23:54
StanOfSky Messages postés 43 Date d'inscription mardi 30 mars 2004 Statut Membre Dernière intervention 7 octobre 2006 - 15 juil. 2004 à 23:54
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/24542-programme-de-tri
https://codes-sources.commentcamarche.net/source/24542-programme-de-tri
15 juil. 2004 à 23:54
en fait au résultat c du linéaire : t'empiles, tu dépiles...
apres tu peu avoir des compilo qui optimisent à fond et optenir le meme résultat en ayant ecrire une fonction récursive qu'en l'ayant déroulé et fait tout meme le systeme de pile.
seul l'assembleur reste la meilleur solution pour etre certain d'avoir une fonctions optimisée a fond ;)
15 juil. 2004 à 13:07
Et si tu regardes les commentaires des codes sources tu remarquera qu'il y en a quelques uns du genre : "ah oui je savais pas, mon prof d'info m'a dit le contraire"
Et merci pour l'info, je vais de ce pas acheter 1 bon livre d'algorithmique, je vais voir si je trouve un de ses bouquins
15 juil. 2004 à 12:35
15 juil. 2004 à 12:22
On m'avait affirmé qu'on ne pouvait pas """"supprimer la recursivité"""" dans le qsort sans deteriorer les performances
15 juil. 2004 à 00:25
15 juil. 2004 à 00:17
la j'ai tenu à faire un code c ansi et clair, mais c'est sur que pour la performance il vaut mieux derouler le code ou specifier les fonctions inline
15 juil. 2004 à 00:15
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.
15 juil. 2004 à 00:12
15 juil. 2004 à 00:03
15 juil. 2004 à 00:02
void swap_i(int *i1, int *i2)
{
int i = *i1;
*i1 = *i2;
*i2 = i;
}
size_t min_i(int *v, size_t size)
{
int min *v, *p v;
size_t i 0, ind_min 0;
while( ++i < size )
if( *(++p) < min )
{
min = *p;
ind_min = i;
}
return ind_min;
}
void sort_i(int *v, size_t size)
{
size_t i;
int *p = v;
for( i = 0; i < size; i++, p++)
swap_i( p, p + min_i(p, size - i) );
}
par exemple
int v[]={1,3,6,5,9,2,7,45,45564,545,54,1,5,26,54,74,5215,54};
sort_i(v, sizeof v / sizeof *v );
14 juil. 2004 à 23:41
14 juil. 2004 à 23:37
14 juil. 2004 à 23:27
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))
14 juil. 2004 à 22:10
14 juil. 2004 à 21:54
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) ?
14 juil. 2004 à 19:02
int *isort(int *tab,size_t size);
14 juil. 2004 à 19:02
Rectif attendue, merci.
BruNews, Admin CS, MVP Visual C++
14 juil. 2004 à 18:58
14 juil. 2004 à 18:49
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).