Voili voilou, comme je ne traine pas depuis longtemps ici, j´aimerais filer quelques petits trucs sympa que j´ai pu trouver en trainant de ci de la, hisoire d´aider comme on m´aide moi.

Je vous propose donc un petit bout de code qui corresppond a l´algorithme dit de " tris rapide"

Largement plus effficace que les algos qu´on trouve habituellement ( j´ai pu le tester moi meme)

Au niveau fonctionnement, il consiste a decouper en tout petit morceau un tres grand tableau et a empiler ca dans la pile du processeur.

La version que je donne fonctionne avec n´importe quel type de variable numerique.

float *sort( float *tab,const int L,const int R)
{

float val,cur;
int g,d;

if(R<=L) return tab;

val=tab[R];
g=L-1;
d=R;
while(g<d)
{ while((tab[++g]<val));
while((tab[--d]>val)&&(d>L));
if(g<d)
{ cur=tab[g];
tab[g]=tab[d];
tab[d]=cur; }
}
cur=tab[g];
tab[g]=tab[R];
tab[R]=cur;
sort(tab,L,g-1);
sort(tab,g+1,R);
}

Pour le faire tourner il suffit d´ecrire:

votre tableau= sort(votre tableau, la limite superieure du tableau, la limite inferieure du tableau( en general 0))

Je l´avais trouve par hasard en ligne mais il est ultime..donc g pas pu m´empecher...

ce cher qsort
l´algo est intéressant, il est en Teta(n*log2(n))
on ne peut pas faire plus rapide...
ça pulvérise l´insert-sorting. ( sauf pour les tableaux déja presque triés ; -p)

L´algo est déja intégré dans stdlib sinon

Que qoui sous Linux ossi? Comment s´apelle la fonction ?

( et dire que j´ai encore fait du code pour rien mdr

Plus exactement a quoi correspond le dernier parametre:

void qsort( void * tab, size_t nt, size_t taille,

int ( *fcmp)(const void *px1, const void *px2));

Vous me faites haluciné, vous parlez chinois ou quoi ?

J´aimerais tant savoir programmer !

Bah si tu veux si je demande c ke je comprend rien non plus...

Sinon c´est sense etre de l´anglais a la base

voila, c´est bien qsort :

void qsort( void * tab, size_t nt, size_t taille,
int ( *fcmp)(const void *px1, const void *px2));

bon, le 1e param est un pointeur sur ton tableau de données a trier, le 2e est le nombre d´élements, le 3e est la taille d´un élément.

Le 4e est super-puissant : c´est un pointeur de fonction.
Dans ce cas, c´est une fonction que tu vas renseigner pour dire COMMENT trier tes éléments :

l´exemple le plus simple :

int trieint(void* a,void* b)
{
int *ia=(int*)a;
int *ib=(int*)b;
return *ib-*ia;
}

qsort(tableaudeint,200,sizeof(int),trieint);

/ * explication en + :

la fonction que tu définies :
int trieint(void* a,void* b)

dit a l´ordi comment trier des int : elle renvoie > 0 si b>a et < 0 si b<a

l´interet est que tu peux trier n´importe quoi

exemple plus puissant :

tu as un tableau :

struct plouf table[50];

avec :

struct plouf
{
int num;
int paf;
};

tu as envie de trier ce tableau selon la valeur de num, autrement classer par ordre croissant les struct plouf, selon leur parametre num :

int triestructplouf(void* a,void* b)
{
struct plouf* ia=(struct plouf*)a;
struct plouf* ib=(struct plouf*)b;
return ib->num-ia->num;
}

qsort(table,50,sizeof(struct plouf),triestructplouf);

et apres cette ligne, ton tableau est bien trié ! !
puissant non ?

Neolo > initie toi tu as toute ta vie devant toi

Oki je v essayer de le faire marcher--> si ca peut rendre mon code plus rapide...

MARCI

et en C++, il existe des classes appelées STL encore + puissantes ! !

Vi c vrai... mais bon la je suis sur un prog en C sous Linux ( vive les stages tout pourris...)

ben alos utilise qsort c´est l´un des algos les puissants puissants, en restant générique, du C

Il semblerait que le Quick Sort n´est pas de complexité O(n*log2(n)), mais de complexité variable selon l´échantillon entre O(n*log2(n)) au mieux à O(n*n) si la liste est déjà triée.

On peut donc faire mieux comme le Heap Sort qui lui reste en O(n*log2(n)).

Ce n´est encore pas là le meilleur algorithme de tri dans toutes les circonstances. Pour peu que l´on puisse faire quelques suppositions sur l´échantillon, on peut descendre à une complexité inférieure à O(n*log2(n)).

Le cas le plus connu étant celui du Count Sort de complexité O(n+k) pour n valeurs discrètes ( des entiers par exemple) et k la valeur maximale.

c´est pour cela que j´ai dit, non pas qu´il était en O(n*log2(n)) , mais en Teta(n*log2(n))

en tout cas, tu as + détaillé la complexité que moi

ouais...un jour je comprendrai...
si si, je progresse; je maitrise maintenant l´essentiel di javascript, je crois....

@fil: là ça rentre déjà dans le domaine de l´informatique théorique ( calculs de complexité, etc...) Ca demande quelques connaissances de maths, donc ne t´inquiète pas ; )

@Nesca: tiens, je ne connaissais pas le Count Sort. C´est vrai que c´est ingénieux quand les conditions s´y prêtent.