Le tri "bulle"

Le principe du tri bulle (bubble sort) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation. La démo ci-après détaille le fonctionnement du tri bulle :

Voici, en pseudo-code, l'algorithme du tri bulle :

PRODECURE Tri_bulle (Tableau a[1:n])

  VARIABLE permut : Booleen;

	REPETER
    		permut = FAUX
    		POUR i VARIANT DE 1 à N-1 FAIRE
        		SI a[i] > a[i+1] ALORS
				echanger a[i] et a[i+1]
				permut = VRAI
			FIN SI
		FIN POUR
	TANT QUE permut = VRAI

FIN PROCEDURE

Il existe beaucoup de variantes du tri bulle. Parmi celles-ci on peut citer le tri bulle "Boustrophedon" ou "bi-directionnel". Le boustrophédon est un mode d'écriture archaïque qui consiste à tracer les lignes alternativement de gauche à droite et de droite à gauche. Cet algorithme de tri fonctionne comme le tri bulle mais change de direction à chaque fois qu'il est parvenu à une extrémité :

On peut également citer le tri "Shuttle" (navette en anglais), encore appelé "tri Shaker". Ce tri fonctionne comme le tri bulle mais effectue un retour arrière dès qu'une permutation est détectée :

Voici, en Caml, l'algorithme du tri bulle :

  let tri_bulle vecteur =
  let permut = ref true in
  begin
	while !permut do
	begin
		permut:=false;
		for i=0 to (vect_length(vecteur)-2) do
			if vecteur.(i)>vecteur.(i+1) then 
			begin
				echange vecteur i (i+1);
				permut:=true;
			end
			else ();
		done;
	end
	done;
  end;
  vecteur;
  where echange vecteur i j =
  let a = vecteur.(i) in
  begin
	vecteur.(i)<-vecteur.(j);
	vecteur.(j)<-a
  end;;
  tri_bulle : 'a vect -> 'a vect = fun