Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Tri à bulles

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Tri à bulles   Ven 9 Fév - 15:40

Le tri à bulle ou tri par propagation est un algorithme de tri très critiqué à cause de sa lenteur d'exécution. Il consiste à faire remonter le plus grand élément du tableau (comme une bulle d'air remonte à la surface) en comparant les éléments successifs. C'est-à-dire qu'on va comparer le 1er et le 2e élément du tableau, conserver le plus grand et puis les échanger s'ils sont désordonnés les uns par rapport aux autres. On recommence cette opération jusqu'à la fin du tableau. Ensuite, il ne reste plus qu'à renouveler cela jusqu'à l'avant-dernière place et ainsi de suite… On arrête quand le tableau à trier est de taille 1 ou qu'on n'a pas fait d'échanges au dernier passage.
Pour trier un tableau A de taille N, le nombre de comparaisons entre paires d'éléments est donc au plus . Le nombre d'échanges de paires d'éléments successifs est égal au nombre de couples (i,j) tels que i < j et A(i) > A(j). Ce nombre d'échanges est indépendant de la manière d'organiser les échanges. Pour un tableau aléatoire, il est en moyenne égal à Le tri à bulle utilisera donc sur un ordinateur un temps proportionnel à N2, ce qui est lent par comparaison avec les algorithmes en nlogn.
Un dérivé du tri à bulle est le shakersort ou tri cocktail. Cette méthode de tri est basée sur une simple observation du comportement du tri à bulle : quand on fait un passage pour trier le maximum du tableau, on a tendance à déplacer les éléments les plus petits du tableau vers le début de celui-ci. Donc l'astuce consiste à alterner les sens de passage de notre bulle. Bien que le nombre d'échanges à effectuer soit identique (voir ci-dessus), on obtient un tri un peu plus rapide que la bulle. En effet, lors des changements de sens, cet algorithme relit les données les plus récentes et qui sont donc encore dans le tampon (cache) de la mémoire. Mais le temps d'exécution est toujours proportionnel à N2 donc médiocre.



Citation :
Une implémentation en Pascal (en ordre croissant)

const MAX = 100; (* MAX = 100 est donné en exemple seulement *)
type tab = array [1..MAX] of integer;
procedure TriBulle(n : integer ; var t : tab);
var i, j, tmp : integer;
begin
(* On va trier les n-1 premiers éléments du tableau *)
for i:=1 to n-1 do begin
j := i;
(* L'éléments d'indice i doit reculer *)
(* Jusqu'à prendre sa place *)
while (j >= 1) and (t[j+1] < t[j]) do begin
tmp := t[j];
t[j] := t[j+1];
t[j+1] := tmp;
j := j - 1;
end;
end;
end;
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: Tri à bulles   Ven 9 Fév - 21:48

merci Mohamed Very Happy
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: Tri à bulles   Sam 10 Fév - 13:34

pas de quoi chaker
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: Tri à bulles   

Revenir en haut Aller en bas
 
Tri à bulles
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: