Tri à bulles avec limitation
du parcours
1.1. Spécification abstraite
1.2. Spécification concrète
1.3. Coeur de l'algorithme
1.4. Procédure pascal
Cliquez ici pour retourner aux thèmes
d'exercices : ....
RAPPEL RESUME : C'est le moins performant de la catégorie
des tris par échange ou sélection.
Son principe est de parcourir la suite (a1, a2, ... , an) en intervertissant toute paire d'éléments consécutifs (ai-1, ai) non ordonnés. Ainsi après un parcours, l'élément maximum se retrouve en an. On suppose que l'ordre s'écrit de gauche à droite (à gauche le plus petit élément, à droite le plus grand élément).
On recommence l'opération avec la nouvelle sous-suite (a1, a2, ... , an-1) , et ainsi de suite jusqu'à épuisement de toutes les sous-suite (la dernière est un couple).
Le nom de tri à bulle vient donc de ce que les plus grands nombres
de chaque sous-suite se déplacent vers la droite successivement
comme des bulles de la gauche vers la droite.
La suite (a1, a2, ... , an) est rangée dans
un tableau T[...] en mémoire centrale. Le tableau contient une partie
triée (en rouge) et une partie non triée (en bleu). On effectue
plusieurs fois le parcours du tableau à trier; le principe de base
étant de ré-ordonner les couples (ai-1, ai)
non classés (en inversion de rang soit ai-1 > ai)
dans la partie non triée du tableau, puis à déplacer
la frontière (le maximum de la sous-suite (a1, a2,
... , an-1)) d'une position :
pour i de n jusquà 1 faire //
recommence une sous-suite (a1, a2, ... , ai)
pour j de 2 jusquà i faire //
échange des couples non classés de la sous-suite
si T[ j-1 ] > T[ j ] alors //
aj-1et
aj
non ordonnés
temp ¬ T[ j-1
] ;
T[ j-1 ] ¬
T[ j ] ;
T[ j ] ¬
temp //on échange les positions de aj-1et
aj
Fsi
fpour
fpour
initial
après un tour
au 8ième tour
....
...........
etc.....
Après un parcours le tableau est partiellement trié mais
il reste des inversions (couples mal classés), tant qu'il reste
des inversion l'on recommence tout le parcours de ce qui n'est pas trié,
ce qui donne une compléxité maximale en O(n²) dans le
cas d'un tableau entièrement désordonné.
rocédure pascal de tri à bulle :
const N = 20;
type
Table = Array[1..N] of integer ;
procedure TriBulle( T : Table );
var i, j, t: integer;
begin
for i:= N downto 1 do
for j := 2 to i do
if T[j-1] > T[j]
then
begin
temp :=
T[j-1];
T[j-1]
:= T[j];
T[j] :=
temp;
end;
end;