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 : ....Hyperlien vers page de cours HTML


RAPPEL RESUME : C'est le moins performant de la catégorie des tris par échange ou sélection.
 
 

pécification abstraite

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.
 

pécification concrète

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 :

 

oeur de l'algorithme :

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;