Discussion :

[dubis]

Bonjour

Pour mon étude personnelle, j'essaye de traduire cet algorithme de tri à bulle :
http://www.gladir.com/CODER/ALGO/tri.htm

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
BOUCLE POUR I <- Nombre d'élément - 2 JUSQU'A 0 PAS -1 FAIRE
            BOUCLE POUR J <- 0 JUSQU'A I PAS 1 FAIRE
                 SI Tableau [ J + 1 ] < Tableau [ J ] ALORS
                           Échanger Tableau [ J + 1 ] avec Tableau [ J ]
                 FIN SI
             FIN BOUCLE POUR
 
FIN BOUCLE POUR

J'ai donc fais le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/perl
use warnings;
use strict;
 
my @tab = qw(101 115 30 63 47 20); 
my $i=$#tab-1 ;
my $j=0;
 
for ( $i , $i=0 , $i--) 
    { for ($j , $j<=$i, $j++) {
            if ( $tab[$j+1] < $tab[$j]) { 
                    $tab[$j+1] = $tab[$j]
                    }
                } 
        print "@tab\n";
        }

Qui me donne ceci :
101 115 115 63 47 20
101 115 115 115 47 20
101 115 115 115 115 20
Ce n'est évidement pas ce j’attends j'aimerais bien visualiser comment le tri se met en place étapes par étapes

J'ai aussi une autre question le script équivalent à celui ci dessus mais écrits comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/perl
use warnings;
use strict;
 
my @tab = qw(101 115 30 63 47 20); 
for ( my $i=$#tab-1 , $i=0 , $i--) 
    { for (my $j=0 , $j<=$i, $j++) {
            if ( $tab[$j+1] < $tab[$j]) { 
                    $tab[$j+1] = $tab[$j]
                    }
                } 
        print "@tab\n";
        }

me donne l'erreur suivante :
Global symbol "$i" requires explicit package name (did you forget to declare "my $i"?) at ./bublesort.pl line 8.
Global symbol "$i" requires explicit package name (did you forget to declare "my $i"?) at ./bublesort.pl line 8.
Global symbol "$j" requires explicit package name (did you forget to declare "my $j"?) at ./bublesort.pl line 9.
Global symbol "$j" requires explicit package name (did you forget to declare "my $j"?) at ./bublesort.pl line 9.

Alors qu'avec le script suivant : http://www.gladir.com/CODER/PERL/tribubble.htm l'expression "for (my $j=0, " fonctionne. Qu'elle sont les différences?

D'avance merci.

[Lolo78]

Bonjour,


je n'ai pas vérifié ton algorithme, mais ta syntaxe pour les boucles for:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
for ( $i , $i=0 , $i--) 
    { for ($j , $j<=$i, $j++) {

est fausse. Ici, la première valeur de $i est -1, donc ta boucle commence assez mal et ça ne peut pas marcher.

Il faut séparer les trois expressions par des points-virgules, pas des virgules, et utiliser un opérateur relationnel (par exemple ==), pas une affectation (=), pour tester la valeur de $i:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for ( $i ; $i == 0 ; $i--) 
    { for ($j ; $j<=$i; $j++) {

[dubis]

Merci de ta réponse

L'expression "JUSQU'A 0" ne s'écrit-elle pas ">=0"

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for ( $i ; $i == 0 ; $i--)

je n'ai pas de sortie

Effectivement dans la boucle for il faut utiliser les points virgule, du coup on peut initialiser $i et $j avec "my"

Finalement je n'ai plus respecté l'algorithme Tri à bulles car j'ai inséré une variable temporaire et je n'ai pas utilisé l'expression "$i==0" mais "$i>=0". Si je respecte ce qui est dit dans la page ou se trouve les différent algorithme de tri avec la variable temporaire nous sommes dans une technique de tri nommée «Shell-Metzner» Du coup mon script est donc venu comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/perl
use warnings;
use strict;
 
my @tab = qw(101 115 30 63 47 20); 
print "@tab\n";
# Dans la boucle for le ";" est tres important
for (my $i=($#tab-2)+1 ; $i>=0 ; $i--) {
    for (my $j=0 ; $j<=$i ; $j++) {
            if ($tab[$j+1] < $tab[$j]) { 
                    my $tmp = $tab[$j+1] ;
                    $tab[$j+1] = $tab[$j] ;
                    $tab[$j] =$tmp;
                    }
                }
        print "@tab\n";
}

Ce qui donne :
101 115 30 63 47 20
101 30 63 47 20 115
30 63 47 20 101 115
30 47 20 63 101 115
30 20 47 63 101 115
20 30 47 63 101 115


Merci de votre aide

[Lolo78]

L'expression "JUSQU'A 0" ne s'écrit-elle pas ">=0"

Si, bien sûr, erreur de copier-coller en reprenant ton code.

Si je comprends bien, ça marche maintenant.

[dubis]

Oui j'ai trouvé une solution ... A moi d'analyser pour ma conclusion

[Lolo78]

Bonsoir,

voici une version plus "perliste" du même algo:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
my @tab = qw(101 115 30 63 47 20); 
for my $i (reverse 0..$#tab-1) {
    for my $j (0..$i) {
        ($tab[$j], $tab[$j+1]) = ($tab[$j+1], $tab[$j]) if ($tab[$j+1] < $tab[$j]);
    }
    print "@tab\n";
}

ce qui donne le même résultat que toi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
101 30 63 47 20 115
30 63 47 20 101 115
30 47 20 63 101 115
30 20 47 63 101 115
20 30 47 63 101 115

Et voici une implémentation de l'algorithme de base (canonique) du tri à bulles:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
my @tab = qw(101 115 30 63 47 20); 
for my $i (0..$#tab) {
    for my $j (0..$#tab-1) {
        ($tab[$j], $tab[$j+1]) = ($tab[$j+1], $tab[$j]) if ($tab[$j+1] < $tab[$j]);
    }
    print "@tab\n";
}

Ce qui affiche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
101 30 63 47 20 115
30 63 47 20 101 115
30 47 20 63 101 115
30 20 47 63 101 115
20 30 47 63 101 115
20 30 47 63 101 115

Pour info, le tri à bulles est réputé inefficace, sa complexité croît avec le carré du nombre d’éléments à trier.

Il existe des variantes plus efficaces (tri de Shell ou tri à peigne) dont la complexité croît généralement avec le nombre d'éléments à trier multiplié par le logarithme de ce même nombre (ce qui est bien meilleur)

Voir par exemple: http://laurent-rosenfeld.developpez....-langage/#L2-2.