Implémentation d'algorithmes classiques/Algorithmes de tri/Tri à bulles
Principe
modifierLe tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide.
let rec bulle l = match l with
[] -> []
| [a] -> [a]
| s::(t::q) -> if s<t then s::(bulle (t::q))
else t::(bulle (s::q));;
let rec tri_bulle l =
if bulle l = l then l else tri_bulle (bulle l) ;;
Version la plus simple.
#include <stdbool.h>/* Permet d'avoir accès au typedef bool (au lieu du type _Bool)
* et aux macros true et false.*/
void tri_a_bulle(int t[], int const n)
{
/* Booléen marquant l'arrêt du tri si le tableau est ordonné */
int en_desordre = 1;
/* Boucle de répétition du tri et le test qui
arrête le tri dès que le tableau est ordonné(en_desordre=false) */
while (en_desordre)
{
/* Supposons le tableau ordonné */
en_desordre = 0;
/* Vérification des éléments des places j et j+1 */
for (int j = 0; j < n-1; j++)
{
/* Si les 2 éléments sont mal triés */
if(t[j] > t[j+1])
{
/* Inversion des 2 éléments */
int tmp = t[j+1];
t[j+1] = t[j];
t[j] = tmp;
/* Le tableau n'est toujours pas trié */
en_desordre = 1;
}
}
}
}
Version optimisée évitant de parcourir la fin du tableau déjà triée.
#include <stdbool.h>/* Permet d'avoir accès au typedef bool (au lieu du type _Bool)
* et aux macros true et false.
*/
void tri_a_bulle(int *t, int const size)
{
bool en_desordre = true;
for (int i = 0; i < size && en_desordre; ++i)
{
en_desordre = false;
for (int j = 1; j < size - i; ++j)
{
if (t[j-1] > t[j])
{
int temp = t[j-1];
t[j-1] = t[j];
t[j] = temp;
en_desordre = true;
}
}
}
}
Version optimisée évitant de parcourir la fin du tableau déjà triée.
#include<algorithm> // pour la fonction swap
void tri_a_bulle(int *t, int const size)
{
bool en_desordre = true;
for (int i = 0; i < size && en_desordre; ++i)
{
en_desordre = false;
for (int j = 1; j < size - i; ++j)
if (t[j-1] > t[j])
{
std::swap(t[j], t[j-1]);
en_desordre = true;
}
}
}
Inclut la saisie du tableau et le tri.
identification division.
program-id. tribulle.
environment division.
data division.
working-storage section.
01 tableau-nombres-info.
05 tabentiers pic 999 occurs 100 times.
77 maxval pic 99 value 5.
77 repete pic 999.
77 i pic 999.
77 j pic 999.
77 temp pic 999.
77 desordre pic 9 value 1.
procedure division.
* saisie des valeurs
perform saisie varying i from 1 by 1
until i greater than maxval
* affichage des valeurs non triées
perform affiche varying i from 1 by 1
until i greater than maxval
accept temp
* tri du tableau
PERFORM boucle
VARYING i FROM 1 BY 1
UNTIL (i GREATER THAN maxval) or (desordre equal 0)
AFTER j from 1 by 1 UNTIL (j GREATER THAN maxval - i).
* affichage des valeurs triées
perform affiche varying i from 1 by 1
until i greater than maxval
accept temp
stop run.
saisie.
display "Entrez nombre " i ": "
accept tabentiers (i).
affiche.
display "nombre " i ": " tabentiers (i).
boucle.
if tabentiers (j) GREATER THAN tabentiers (j + 1)
move tabentiers (j) to temp
move tabentiers (j + 1) to tabentiers (j)
move temp to tabentiers (j + 1)
move 1 to desordre.
Tri de tableau
modifierpublic static void triBulle(int[] tableau)
{
int longueur=tableau.Length;
boolean permut;
do
{
// hypothèse : le tableau est trié
permut=false;
for (int i=0 ; i<longueur-1 ; i++)
{
// Teste si 2 éléments successifs sont dans le bon ordre ou non
if (tableau[i] > tableau[i+1])
{
// s'ils ne le sont pas on échange leurs positions
//la méthode echanger doit être implémenté
echanger(tableau,i,i+1);
permut=true;
}
}
}
while(permut);
}
Tri de vector
modifierEn Java, marche aussi sous J2ME sans structure do+while ou tableau, avec un Vector de My_obj :
public Vector tri_bulle (Vector vec)
{
int limit = vec.size();
boolean permutation = true;
My_Obj obj_one;
My_Obj obj_two;
while (permutation)
{
permutation = false;
for (int i=0 ; i<limit-1 ; i++)
{
obj_one = (My_obj)vec.elementAt(i);
obj_two = (My_obj)vec.elementAt(i+1);
if (obj_one.get_COMPARE_VALUE() > obj_two.get_COMPARE_VALUE())
{
vec.setElementAt(obj_one, i+1);
vec.setElementAt(obj_two, i);
permutation = true;
}
}
}
return vec;
}
Version optimisée évitant de parcourir la fin du tableau déjà triée.
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,tmp: integer;permut:boolean;
begin (* On a choisi le sens croissant pour trier le tableau *)
repeat
permut:=false;
for i:=1 to (n-1) do
begin
if(t[i] > t[i+1]) then
begin
tmp := t[i];
t[i] := t[i + 1];
t[i+1] := tmp;
permut:=true;
end;
end;
n:=n-1;
until(non (permut)) or (n=1);
end;
function bubble_sort($array)
{
$i = count($array);
if ($i <= 0) return false;
do
{
$ok = false;
for($j=$i-1; $j!=0; $j--)
{
if ($array[$j] < $array[$j-1])
{
$tmp = $array[$j];
$array[$j] = $array[$j-1];
$array[$j-1] = $tmp;
$ok = true;
}
}
}
while($ok);
return $array;
}
def bubble_sort(data):
n = len(data)
swapped_elements = True
while swapped_elements:
swapped_elements = False
for j in range(0, n-1):
if data[j] > data[j+1]:
swapped_elements = True
data[j],data[j+1] = data[j+1],data[j]
return data
Tout ou partie de cette page est issue de l'article Wikipédia « Tri à bulles » dans sa version du 23/04/2010.