 |
| | | | | | | | Bubble Sort / Tri à Bulles
| | | | | | |
Le principe est simple : c'est de la comparaison élément par élément en réduisant à chaque fois l'intervalle de tri.
C'est à dire qu'au début on parcours tout le tableau, on déplace l'élément le plus grand vers la droite (ou le plus petit en
fonction du type de tri), si il y a une inversion (le tableau n'est donc pas trié), sinon, on peut s'arrêter.
k <- Nombre d'élément du tableau
Permut <- k
REPETER
k <- permut - 1
POUR J ALLANT de 1 à k FAIRE
SI [ Elément (J) > Elément (J+1) ] ALORS
tempValue <- Elément (J)
Elément (J) <- Elément (J+1)
Elément (J+1) <- tempValue
permut <- J;
FIN SI
FIN POUR
JUSQU'A [ Permut > k ];
Variables :
| Nom | Fonction |
| K | Compteur correspondant au nombre de cases restant à trier |
| Permut | Numéro de la case de la dernière permutation |
| J | Compteur courant dans le tableau |
| Element | Tableau (ou liste, pile...) à trier |
| tempValue | Valeur temporaire afin de pouvoir inverser les 2 variables |
Le tableau est initialisé à :
|
| Etape 1 |
Initialisation | k = 4, Permut = 5, J va de 1 à 4 |
| J=1 | Rien à faire |
| J=2 |
Permut = 2 |
| J=3 |
Permut = 3 |
| J=4 |
Permut = 4 |
| Etape 2 |
Initialisation | k = 3, Permut = 4, J va de 1 à 3 |
| J=1 | Rien à faire |
| J=2 | Rien à faire |
| J=3 |
Permut = 3 |
| Etape 3 |
Initialisation | k = 2, Permut = 3, J va de 1 à 2 |
| J=1 | Rien à faire |
| J=2 |
Permut = 2 |
| Etape 4 |
Initialisation | k = 1, Permut = 2, J va de 1 à 1 |
| J=1 | Rien à faire |
Le tableau est trié :
Il a suffit de 5 permutations pour le trier.
|
$k = 4;
$permut = $k;
do {
$k = $permut - 1;
for ($j=1; $j<=$k; $j++) {
if ($topDest[$j] > $topDest[$j+1]) {
$tempValue = $topDest[$j];
$topDest[$j] = $topDest[$j+1];
$topDest[$j+1] = $tempValue;
$permut = $j;
}
}
} while $permut <= $k;
k = 4
permut = k
do
k = permut - 1;
for j=1 to k
if (topDest[j] > topDest[j+1]) {
tempValue = topDest[j];
topDest[j] = topDest[j+1];
topDest[j+1] = tempValue;
permut = j;
}
next loop
until ( permut > k );
k := 4;
Permut := k;
repeat
k := permut - 1;
for j:=1 to k do
if (topDest[j] > topDest[j+1]) then
begin
tempValue := topDest[j];
topDest[j] := topDest[j+1];
topDest[j+1] := tempValue;
permut := j;
end;
until Permut > k;
int k=4;
int permut=k;
String tempValue;
do {
k = permut-1;
for (int j=0; j<=k; j++) {
if (((String) logValid.elementAt(j)).compareTo(logValid.elementAt(j+1)) > 0) {
tempValue = (String) logValid.elementAt(j);
logValid.setElementAt(logValid.elementAt(j+1),j);
logValid.setElementAt(tempValue,j+1);
permut = j;
}
}
} while (permut <= k);
|
