Fonction pour ordonner des tableaux

Sujet résolu

7 juin 2006 à 4:19:14

Hello!

Voici comment j'ai résolu l'exercice 5 du chapitre sur les tableaux.
Ma fonction orderTable qui les valeurs d'un tableau en ordre croissant. ùelle fonctionne j'aimerais juste savoir s'il y a des améliorations que je pourrais apporter au niveau optimisation ou simplification du code.

void orderTable(long table[], long tableSize)
{
long i,j,temp, position = 0;

for (j=tableSize; j>0; j--)
{
temp = 0;
for(i=j; i>=0; i--)
{
if(table[i]>=temp)
{
temp=table[i];
position = i;
}
}
table[position] = table[j];
table[j] = temp;
}
}

merci
Fred

Superman

7 juin 2006 à 16:27:18

UP, j'ai pas posté pendant que c'était achalandé, ça m'apprendra !!

Anonyme

7 juin 2006 à 18:01:25

C'est la méthode que j'avais eu.
Mais désolé je ne sais pas si ça peut être améliorer, il y a peut-être des fonctions. Désolé.

1h0ma5

HanLee

7 juin 2006 à 18:09:48

Hum, apparemment c'est un tri par sélection.
Ya une erreur dans ton algorithme, parce que tu initialises temp avec 0. Et si tout ton tableau ne contient que des nombres négatifs, ta fonction ne marche pas. Il faut nécessairement initialiser ton temp avec un élément de ton tableau :).

AoSiX

8 juin 2006 à 1:57:03

et elle n'est pas de toi je l'ai deja vu sur le net

Superman

8 juin 2006 à 5:08:42

Ah merci Hanlee, je vais voir ça maintenant!

A06 -> oui c'est vrai t'as raison, je l'ai prise d'un site et je l'ai postée ici pour avoir l'air d'un pro du C!

... non mais...

EDIT:

voici mon nouveau code:

void orderTable(long table[], long tableSize)
{
long i,j,temp, position = 0;
for (j=0; j<(tableSize-1); j++)
{

// On initialise temp et position a la premiere case testée
temp = table[j];
position = j;

for(i=j; i<tableSize; i++)
{
if(table[i]<temp)
{
temp=table[i];
position = i;
}
}

table[position] = table[j];
table[j] = temp;
}

}

Il marche avec des nombres négatifs cette fois. Exemple:

bluestorm

8 juin 2006 à 7:27:05

Pour améliorer les performances, il faut changer d'algorithme de tri. Celui là est un "tri quadratique" c'est à dire qu'il effectue approximativement N² opération, si N est la taille du tableau (tu as deux boucles encastrées, la première de tablesize, et la seconde qui fait un peu moins que tablesize).

Pour plus d'informations sur la complexité de ton algorithme, je t'invite à lire http://www.siteduzero.com/tuto-3-4644-1-algorithmique-tri-par-insertion.html.

Maintenant, pour augmenter tes performances, tu peux utiliser des tris "logarithmique", c'est à dire qui s'executent en N*lg(N) opérations environ, ce qui est beaucoup plus rapide que N*N, parce que lg(N) est une fonction (si tu ne la connais pas) qui augment très, très lentement (lg(un milliard) c'est environ 30).

Tu devrais donc te renseigner sur les trois tris logarithmiques les plus connus, le tri par fusion (mergesort), le tri par tas (heapsort), et le tri rapide (quicksort, qui n'est pas exactement logarithmique, mais presque).

Je pense que le plus facile à coder et comprendre pour commencer est le tri par fusion.

http://fr.wikipedia.org/wiki/Tri#Exemples_d.27algorithmes_de_tri

HanLee

8 juin 2006 à 12:58:43

Son tri c'est pas du tri par insertion au fait, donc la démonstration de la complexité n'est pas exactement la bonne... ;).
Mais bon, c'est quand même du O(N²).

bluestorm

8 juin 2006 à 13:27:21

Bah au lieu de faire 1+2+3+4+...+N, il fait N+(N-1)+...+1. Donc la démonstration reste valable, et son tri équivaut à un tri par insertion visiblement.

Superman

8 juin 2006 à 16:23:43

Merci Bluestorm..
Jsuis content de savoir que ma fonction etait pas si mal compte tenu de mes connaissances en C... Je vais approfondir ça avec le lien que tu m'as proposer. J'ai toujours été pas pire dans les log, on va voir si mes cours de maths vont payer!!