Trier un tableau par ordre croissant

Version imprimable

Bonjour à tous,

je n'arrive pas à trouver comment trier un tableau. J'ai fais pour l'instant ça en PHP:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// le tableau avec les valeurs à trier 
$tab[0] = 8; 
$tab[1] = 5; 
$tab[2] = 4; 
$tab[3] = 9; 
 
$nbvaleurs = 4-1; // le premier indice est 0, pas 1. je ne met pas 3 tout de suite pour me repérer plus facilement ;o) 
 
///////////////////// 
// TRI CROISSANT // 
///////////////////// 
for ($i = 0; $i < $nbvaleurs; $i++) 
{ 
   $flag = $nbvaleurs; 
   for($j = 0; $j <$nbvaleurs; $j++) 
   { 
         // trouver le comparé 
      $Compare = $tab[$j]; 
         // trouver le comparant 
      $flag = $flag - 1; 
      $NbComparant = $nbvaleurs - $flag; 
      $Comparant = $tab[$NbComparant]; 
         // sauvegarder le comparant 
      $SavComparant = $tab[$NbComparant]; 
 
         // COMPARER 
      if($Compare>$Comparant) 
      { 
            // inverser le comparant et le comparé 
         $tab[$NbComparant] = $tab[$i]; 
         $tab[$i] = $SavComparant; 
      } 
   } 
} 
////////////////////

Ca trie bien comme il le faut, mais seulement quand il y a moins de 5 valeurs à trier 8O . Est-ce que vous avez une idée pour arranger tout ça?

Merci d'avance :wink:

PS: j'ai posté également dans le forum Autres langages et outils. On m'a conseillé de poster ici, donc j'ai mis l'autre sujet en délestage... (Pas taper! pas Multipost! Nooon! Aïe! maiheuuuuuu! :lol: )

25/10/2004, 01h24
nako

salut,
il existe une (plusieurs même) fonction(s) pour trier un tableau en PHP :
http://www.php.net/manual/fr/function.sort.php entres autres.
Maintenant, si tu veux programmer tout de même le tri toi-même, fais une recherche sur google sur quicksort ou tri à bulle, ou sur méthodes de tris ... la littérature (comme on dit) est abondante sur le sujet.
a+
25/10/2004, 01h49
Halleck

Super! Merci beaucoup! Vraiement, depuis le temps que je cherche, je n'ai jamais trouvé cette fonction (Une recherche avec google sur "tri tableau php" donne pas grand chose :wink: .

Mais ce ci dit, c'est vrai que ca m'interesserait de savoir comment on fait. Si vous pouviez juste m'indiquer pourquoi j'ai faux dans mon code... Merci d'avance :wink:
25/10/2004, 15h58
Médiat

Je n'ai pas vérifié, mais en écrivant
$nbvaleurs = 4-1 et $i < $nbvaleurs, il me semble que tu n'atteindras jamais $tab[3], qui ne sera jamais comparé.
26/10/2004, 19h42
Halleck

Ben... je crois que si, vu que pour le tableau que j'ai mis en exemple ici, le tri s'effectue bien. 8O . Ou bien c'est une coïncidence? j'avoue être un littéarire dans l'âme, donc pas très fort en math, il se peut donc que je me trompe :wink:
26/10/2004, 21h27
gangsoleil

Le tri s'effectue bien car la dernière case contient la plus haute valeure...
Essaie en remplacant '9' par '1', et dis nous le résultat stp ;)
26/10/2004, 22h58
Halleck

J'ai mis "1" à la place de "9", le tri s'effectue bien:

Citation:

1458

Ca ne vient pas de ça donc 8O ...
26/10/2004, 23h39
plegat
Salut,

En regardant rapidement, ton code marche bien pour 4 valeurs car il regarde les valeurs de rang 0 à 2, et les compare avec toutes les valeurs de rang supérieur jusqu'au rang 3.

Donc normalement ça devrait marcher avec un tableau ayant plus d'éléments, en prenant soin de remplacer le 4 dans ta ligne
Code:

1 2 $nbvaleurs = 4-1;
par la valeur qui convient (=nombre d'éléments dans ton tableau)
27/10/2004, 00h00
nako

note bien que plutôt que de faire ta soustraction, tu as une fonction en PHP qui te compte le nombre d'éléments d'un tableau : count

donc ton code devient :

Code:

$nbvaleurs = count($tab);

C'est bien de vouloir tout faire pour comprendre, mais il ne faut pas oublier que les langages récents contiennent nativement un certain nombres de fonctions. (mais j'ai bien compris que dans ton cas, tu souhaite apprendre)
a+

Dans la mesure ou je parle pas PHP, voici comment je coderai un tri :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
 
 
//remplissage du tableau
int i=0, j=0, taille=0;
taille = ... // nombre_d'elements_du_tableau
 
Tanque (j < taille-1) faire    // Pour chaque élément
   Pour (i = 0 à taille-2)    // taille-2 car je compare tab[i] à tab[i+1]
      Si ( tab[i] > tab[i+1] )    // Si on n'a pas le bon ordre
         int tempo = tab[i] ;     // on stocke la valeur de tab[i]
         tab[i] = tab[i+1] ;       // On change
         tab[i+1] = tempo ;      // on restitue la valeur sauvée
      FinSi ;
   FinPour ;
   j = j+1 ; // ne pas oublier d'incrémenter j
FinTantque

Ca fait longtemps que j'ai pas codé un tri, donc il est possible (et même probable) que cet algo ne soit pas fonctionnel. Cependant, j'espère qu'il t'aidera à mieux cibler ton erreur (on sait jamais).

27/10/2004, 02h58
Halleck

gangsoleil -> Je ne vois pas de différence avec mon code, sauf le Int. Pour moi Int permet de donner l'arrondi d'un nombre, je suppose qu'ici ce n'est pas le cas; à quoi sert-il alors? Juste à indiquer qu'on a une égalité?

Citation:

note bien que plutôt que de faire ta soustraction, tu as une fonction en PHP qui te compte le nombre d'éléments d'un tableau : count

Ah ben oui, j'avais oublié. Merci :wink:

Citation:

C'est bien de vouloir tout faire pour comprendre, mais il ne faut pas oublier que les langages récents contiennent nativement un certain nombres de fonctions. (mais j'ai bien compris que dans ton cas, tu souhaite apprendre)

Non seulement je veux apprendre, mais surtout je programme aussi en QBasic, et je ne crois pas qu'il y ait des fonctions de tri dans ce langage

Citation:

Donc normalement ça devrait marcher avec un tableau ayant plus d'éléments, en prenant soin de remplacer le 4 dans ta ligne

Ben non justement. Le tri donne n'importe quoi quand le tableau est trop grand 8O

En tous cas, merci à tous de m'aider :wink:

Citation:

Envoyé par Halleck

gangsoleil -> Je ne vois pas de différence avec mon code, sauf le Int. Pour moi Int permet de donner l'arrondi d'un nombre, je suppose qu'ici ce n'est pas le cas; à quoi sert-il alors? Juste à indiquer qu'on a une égalité?

non, ici le int déclare une variable de type entier, qui sert à sauver tab[i] pour échanger la valeur avec tab[j].

Ceci étant dit, ton problème vient des indices de boucles :

Si max est le nombre d'éléments dans le tableau, donc indices de 0 à max -1, tu devrais avoir:
Code:

1 2 3 4 5 6 7 8 9 10 pour i = 0 à max - 2 faire pour j = i + 1 à max - 1 faire si tab[i] > tab[j] faire tampon = tab[i] tab[i] = tab[j] tab[j] = tampon fin si fin pour j fin pour i
avec :
- boucle i de 0 à max - 2 pour respecter les indices, et i n'ayant pas besoin d'aller lire la dernière valeur, on laisse ce soin à la boucle j
- boucle j de i+1 à max - 1 : on n'a pas besoin de se préoccuper des indices <= i dans cette boucle, et elle va jusqu'à la dernière valeur.

et ton code marche avec 4 valeurs, car avec tes calculs d'indices etc..., tu balayes de fait tout le tableau, mais ce n'est plus le cas avec plus de valeurs.

27/10/2004, 14h40
PINGOUIN_GEANT

je pense que tu fais un "faux" tri à bulles, ta première boucle devrait aller dans le sens inverse.
Autrement pour d'autres fonctions de tri, tu peux faire une recherche sur:
tri par insertion, tri à bulles, tri rapide, tri fusion...

edit: désolé, j'ai mal regardé => à chaque itération sur le premier indice d'un tri à bulles, un élément à la fin est bien placé donc tu peux arrêter à i.
d'ailleurs je ne connais pas le php mais c'est bizarre que ton indice i intervient dans des if.
28/10/2004, 18h32
Halleck

je vais essayer de modifier mes indices donc selon les conseils de thewho, mais par contre PINGUIN_GEANT, désolé, j'ai rien compris à tes histoires de "bulles", "tri par insertion", etc...

Et pourquoi est-ce bizarre que mon indice i interviennent dans des if? :oops:

Re: Trier un tableau par ordre croissant

Citation:
Envoyé par Halleck
Code:

1 2 3 4 5 6 7 8 9 10 11 // COMPARER if($Compare>$Comparant) { // inverser le comparant et le comparé $tab[$NbComparant] = $tab[$i]; $tab[$i] = $SavComparant; } } } ////////////////////
je ne comprends pas trop ces lignes, comme je ne connais pas le php.
A quoi servent-elles ?
quand tu regardes le code de gangsoleil (typiqument un tri à bulles), seul le deuxième indice intervient pour les comparaisons.

quant à tri machin, tri bidule... ce sont juste des noms de tris, donc si tu veux des infos complémentaires sur d'autres possibilités tu sais ce qu'il te reste à faire.

Re: Trier un tableau par ordre croissant

Citation:
Envoyé par PINGOUIN_GEANT
Citation:
Envoyé par Halleck
Code:

1 2 3 4 5 6 7 8 9 10 11 // COMPARER if($Compare>$Comparant) { // inverser le comparant et le comparé $tab[$NbComparant] = $tab[$i]; $tab[$i] = $SavComparant; } } } ////////////////////
je ne comprends pas trop ces lignes, comme je ne connais pas le php.
A quoi servent-elles ?
Le PHP n'intervient pas trop ici, juste pour les $ je pense... Dans ces lignes j'attribue la valeur du comparant au comparé si le permier est plus grand que le second. En gros j'inverse la position des valeurs comparées.

Pour le "tri par insertion", etc..., j'ai trouvé ce que ca signifiait dans un exemple fourni par défaut avec QBasic 4.5, avec plein de tris différents. Je comprend la démo, mais les algorythmes en eux-mêmes non :oops:

Je vais essayer de comprednre ces exemple, et en attendant je methttp://www.developpez.net/forums/images/resolu.gif. Si jamais je n'y arrive pas, je reposte ici.

Merci à tous pour votre aide :wink: