Aller au contenu

Implémentation d'algorithmes classiques/Algorithmes de tri/Tri à bulles

Un livre de Wikilivres.

Wikipédia propose un article sur : « Tri à bulles ».

Le 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.

Version Caml récursive

[modifier | modifier le wikicode]
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

[modifier | modifier le wikicode]
public 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);
}

En 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.