Qu'est ce que le tri a bulle et le tri par extraction??

bon alors le tri à bule voilà le principe:
 
 
imagine un tableau:
 
5 8 4 9 2
 
tu voudrai le trier, la méthode consiste à faire remonter l'élément le plus petit du tableau (ou le plus grand) vers ça place, comme une bulle, par des passes successives, ce qui donne sur l'exemple:
 
passe 1:
 
5 8 4 9 2  
on compare 5 et 8, 5 < 8 donc on touche pas
on compare ensuite 8 et 4, 4 < 8 donc on interverti:
 
5 4 8 9 2
 
on compare 8 et 9, pas de changement
 
on compare 9 et 2, 2 < 9 donc:
 
5 4 8 2 9
 
9 a ateind ça place on ne le comparera plus pour gagner du temps (en fait à chaque passe le plus gros se retrouve à la fin)
 
passe 2:
 
4 < 5: 4 5 8 2 9
5 < 8: pas de changement
2 < 8: 4 5 2 8 9
 
on a fini pour cette passe
 
passe 3:
 
4 < 5: pas de changement
2 < 5: 4 2 5 8 9
 
fini
 
passe 4:
 
2 < 4: 2 4 5 8 9
 
fini
 
passe 5:
 
plus de changement à faire le tri est fini
 
le tri par extraction je me souvient plus

le tri par extraction simple c presque la meme chose mais ds le sens contrtaire! je m'explique :
 
soit une liste de nbr : 60 15 7 8
 
on compare 60 et 7
on regarde le + petit et on le met en 1er lieu
 
=> (je compaer les chiffre souligner puis je les inverse si le faut)
7 60 15 8
7 60 15 8
 
ici on sait deja ke 7 est le plus petit => on y touch + !
 
7 60 15 8
7 15 60 8
 
15 est le plus petit des nbr non triés !
7 8 60 15
 
=> version finale : 7 8 15 60

[edtdd]--Message édité par kangol_from_PPC--[/edtdd]

voici 2 algo en pseudo code pour ces methode de tri :
 
tri a bulle :
--------------
vec=vecteur contenant toutes les valeur a trier
i=longueur(vec)
tant que i>0
faire
      pour j,1->i-1,j=j+1
      faire
            si vec[j]>vec[j+1]
            alors
                 permuter vec[j] et vec[j+1]
       fin boucle
       i=i-1
fin boucle
 
--------------------------------------------------------
tri par extraction simple:
--------------------------
 
vec=vecteur contenant toutes les valeur a trier
len=longueur(vec)
x=1
tant que x<=(len-1)
faire
      i=x+1
      tant que i<=len
      faire
           si vec[i]<vec[x]
           alors
                permuter vec[i] et vec[x]
           i=i+1
      fin boucle
      x=x+1
fin boucle
--------------------------------------------------
 
voila !

on peut améliorer le tri à bulle en positionnant un booléan qui sert à mémoriser si lors d'une passe on a fait une modification ou pas. si à la fin d'une passe on n'a fait aucune permutation alors le tri est terminé.
 
vec=vecteur contenant toutes les valeur a trier  
i=longueur(vec)  
test=vrai
tant que i>0 et test
faire  
     test=faux
     pour j,1->i-1,j=j+1  
     faire  
           si vec[j]>vec[j+1]  
           alors  
                permuter vec[j] et vec[j+1]  
  test=vrai
           fsi
      fin boucle  
      i=i-1  
fin boucle  
 
question : tri par extraction = tri par insertion ?
 
parce que ce vous donnez comme code, pour moi, c'est le tri par insertion

le tri a bulle c'est "j'oublie"
 
A noter une variante du tri par insertion
le tri shell
ainsi que des methodes de tri
utilisees regulierement comme QuickSort
(consideree comme l'une des plus efficaces
sur des listes quelconques)  
ou encore des particularites  
comme le tri radix, heritee de l'histoire de
la mecanographie (trieuses mecaniques).
 
LEGREG