Algorithme de tri de tableau
De l'algorithme au Java & C

Tri par sélection du minimum

Tri par sélection croisée

Tri Bulle

Ce tutoriel, a pour but de vous entraîner dans l'élaboration d'algorithme qui reste tout de même assez simple puis de passer de l'alogorithme à la programmation. J'ai choisi un langage séquentiel très connu et très pratiqué : le C, ainsi qu'un langage objet : Java, afin de vous montrer les différences. J'ai opté pour la facilité et la compréhension, c'est pour cette raison que j'ai fixé une taille maximale sous forme de constante pour les tableaux car en effet il est très complexe en C de créer des tableaux dynamiques, par contre en Java, je dois avouer que ce n'est pas très judicieux de ma part car on peut faire appel au constructeur pour fixer la taille du tableau en y ajoutant un paramètre. Je vous laisse donc faire à votre guise !

Tri par sélection du minimum

Décrire une fonction qui trie par ordre croissant les éléments d'un tableau selon le principe suivant : on parcourt le tableau pour repérer le minimum puis on l'échange avec la première valeur non encore triée. On répète ce processus n-1 fois pour un tableau de n éléments.

Exemple :

tableau initial :

53

23

89

13

97

5

18

46

après un premier parcours :

5

23

89

13

97

53

18

46

après un second parcours :

5

13

89

23

97

53

18

46

Algorithme

  fonction trierParSelectionDuMinimum(t InOut : tableau entier[0..n-1], n : entier) 
  	début 
  		pour i de 0 à n-2 faire 
  			min_found <- faux 
  			mimi <- t[i] 
  			pour j de i+1 à n-1 faire 
  				si mini > t[j] 
  					alors 
  						mini <- t[j] 
  						indice <- j 
  						min_found <- vrai
  				fsi 
  			fpour 
  			si min_found = vrai 
  				alors 
  					t[indice] <- t[i] 
  					t[i] <- mini 
  			fsi 
  		fpour 
  	fin 

	Lexique :
	- t : tableau entier[0..n-1], tableau à trier 
	- n : entier, taille du tableau fourni en paramètre 
	- i : entier, variable d'itération 
	- j : entier, variable d'itération 
	- mini : entier, valeur minimum trouvée dans la tableau à chaque itération 
	- indice : entier, indice du tableau où a été trouvé le minimum 
	- min_found : booléen, vrai si un minimum a été trouvé dans le tableau

Programme en Java

  
public class TrierTableau {
    private int[] tableau;
    public static int taille_tableau=10;

    public TrierTableau () {
        this.tableau = new int[this.taille_tableau];
    }

    public void initialiserTableau() {
        int valeur;
        for(int i=0; i<this.taille_tableau; i++)
        {
            System.out.println("Veuillez entrez la "+(i+1)+"e valeur :");
            valeur = Clavier.lireInt();
            this.tableau[i] = valeur;
        }
    }

    public void trierParSelectionDuMinimum() {
        int mini, indice=0;
        boolean min_found;
        for(int i=0; i<=this.taille_tableau-2; i++)
        {
            mini = this.tableau[i];
            min_found = false;
            for(int j=i+1; j<=this.taille_tableau-1; j++)
            {
                if(mini>this.tableau[j])
                {
                    mini = this.tableau[j];
                    min_found = true;
                    indice = j;
                }
            }
            if (min_found)
            {
                this.tableau[indice] = this.tableau[i];
                this.tableau[i] = mini;
            }
        }
    }

    public String toString() {
        String chaine="";
        for(int i=0; i<this.taille_tableau; i++)
        {
            chaine += this.tableau[i]+"\n";
        }
        return chaine;
    }

    public static void main(String[] args) {
        TrierTableau tabInt = new TrierTableau();
        tabInt.initialiserTableau();
        System.out.println("\n\nLe tableau avant le tri :");
        System.out.println(tabInt);
        tabInt.trierParSelectionDuMinimum();
        System.out.println("\n\nLe tableau apres tri :");
        System.out.println(tabInt);
        System.exit(0);
    }
}

Programme en C

#include <stdio.h>

#define NBMAX 10


void afficherTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("t[%d] = %d\n", i, tab[i]);
	}
}


void remplirTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("Veuillez saisir la %deme valeur :\n", i+1);
		scanf("%d", &tab[i]);
	}
}


void trierParSelectionDuMinimum(int tab[])
{
	int i, j, indice, mini, min_found;
	for(i=0; i<=NBMAX-2; i++)
	{
		min_found=0;
		mini=tab[i];
		for(j=i+1; j<=NBMAX-1; j++)
		{
			if(mini>tab[j])
			{
				mini=tab[j];
				min_found=1;
				indice=j;
			}
		}
		if(min_found==1)
		{
			tab[indice]=tab[i];
			tab[i]=mini;
		}
	}
}


void main(void)
{
    int tableau[NBMAX];
    remplirTableau(tableau);
    printf("\n");
    afficherTableau(tableau);
    printf("\n");
    trierParSelectionDuMinimum(tableau);
    printf("\n");
    afficherTableau(tableau);
}

Tri par sélection croisée

Décrire la fonction triParSelectionCroisee qui réalise le tri du tableau par sélection du minimum et du maximum. On parcourt le tableau pour repérer à la fois son maximum et son minimum, puis on échange ces deux valeurs avec respectivement la première et la dernière valeur non encore triées. En procédant (n-1)/2 fois pour un tableau de n éléments, on obtient ainsi un tableau trié. Attention : si l'élément maximum courant se trouve dans la première case non encore triée, et si cette case est d'abord permutée avec celle qui contient l'élément minimal courant, alors l'élément maximal se retrouve dans la case qui contient l'élément minimal !

Exemple :

tableau initial :

53

23

89

13

97

5

18

46

après un premier parcours :

5

23

89

13

46

53

18

97

après un second parcours :

5

13

18

23

46

53

89

97

Algorithme

fonction triParSelectionCroisee(t InOut : tableau entier[0..n-1], n : entier)
    début
        pour i de 0 à (n-1)/2 faire
            min <- max <- t[i]
            indicemax <- indicemin <- -1
            pour j de i+1 à n-i-1 faire
                si min > t[j]
                    alors
                        min <- t[j]
                        indicemin <- j
                fsi
                si max < t[j]
                    alors
                        max <- t[j]
                        indicemax <- j
                fsi
            fpour
            si indicemin <> -1
                alors
                    t[indicemin] <- t[i]
                    t[i] <- min
                    si indicemax = i
                        alors indicemax <- indicemin
                    fsi
            fsi
        fpour
    fin
	
    Lexique :
	- min : entier, minimum trouvé à chaque parcours du tableau
	- max : entier, maximum trouvé à chaque parcours du tableau
	- indicemin : entier, contient l'indice où se situe le minimum s'il a été
	              trouvé sinon -1
	- indicemax : entier, contient l'indice où se situe le maximum s'il a été
	              trouvé sinon -1
	- i : entier, variable d'itération
	- j : entier, variable d'itération
	- t : tableau entier[0..n-1], tableau à trier
	- n : entier, taille du tableau fourni en paramètre

Programme en Java

public class TrierTableau {
    private int[] tableau;
    public static int taille_tableau=8;

    public TrierTableau () {
        this.tableau = new int[this.taille_tableau];
    }

    public void initialiserTableau() {
        int valeur;
        for(int i=0; i<this.taille_tableau; i++)
        {
            System.out.println("Veuillez entrez la "+(i+1)+"e valeur :");
            valeur = Clavier.lireInt();
            this.tableau[i] = valeur;
        }
    }


    public void trierParSelectionCroisee() {
        int min, max, indicemin, indicemax;
        for(int i=0; i <= (this.taille_tableau-1)/2; i++)
        {
            min = max = this.tableau[i];
            indicemin = indicemax = -1;
            for(int j = i+1; j <= this.taille_tableau-1-i; j++)
            {
                if(min < this.tableau[j])
                {
                    min = this.tableau[j];
                    indicemin = j;
                }
                if(max > this.tableau[j])
                {
                    max = this.tableau[j];
                    indicemax = j;
                }
            }
            if(indicemin != -1)
            {
                this.tableau[indicemin] = this.tableau[i];
                this.tableau[i] = min;
                if(indicemax == i)
                {
                    indicemax = indicemin;
                }
            }
            if(indicemax != -1)
            {
                this.tableau[indicemax] = this.tableau[this.taille_tableau-i-1];
                this.tableau[this.taille_tableau-i-1] = max;
            }
        }
    }


    public String toString() {
        String chaine="";
        for(int i=0; i<this.taille_tableau; i++)
        {
            chaine += this.tableau[i]+"\n";
        }
        return chaine;
    }

    public static void main(String[] args) {
        TrierTableau tabInt = new TrierTableau();
        tabInt.initialiserTableau();
        System.out.println("\n\nLe tableau avant le tri :");
        System.out.println(tabInt);
        tabInt.trierParSelectionCroisee();
        System.out.println("\n\nLe tableau apres tri :");
        System.out.println(tabInt);
        System.exit(0);
    }
}

Programme en C

#include <stdio.h>

#define NBMAX 8


void afficherTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("t[%d] = %d\n", i, tab[i]);
	}
}


void remplirTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("Veuillez saisir la %deme valeur :\n", i+1);
		scanf("%d", &tab[i]);
	}
}


void trierParSelectionCroisee (int tab[])
{
	int i, j, min, max, indicemin, indicemax;
	for(i=0; i<=(NBMAX-1)/2; i++)
	{
		min=max=tab[i];
		indicemin=indicemax=-1;
		for(j=i+1; j<=NBMAX-1-i; j++)
		{
			if(min>tab[j])
			{
				min=tab[j];
				indicemin=j;
			}
			if(max<tab[j])
			{
				max=tab[j];
				indicemax=j;
			}
		}
		if(indicemin!=-1)
		{
			tab[indicemin]=tab[i];
			tab[i]=min;
			if(indicemax==i)
			{
				indicemax=indicemin;
			}
		}
		if(indicemax!=-1)
		{
			tab[indicemax]=tab[NBMAX-i-1];
			tab[NBMAX-i-1]=max;
		}
	}
}


void main(void)
{
	int tableau[NBMAX];
	remplirTableau(tableau);
	printf("\n");
	afficherTableau(tableau);
	printf("\n");
	trierParSelectionCroisee(tableau);
	printf("\n");
	afficherTableau(tableau);
}

Tri bulle

Décrire la fonction triCroissantBulle. On parcourt le tableau en échangeant deux cases consécutives mal ordonnées. On répète le procédé tant que le tableau n'est pas trié.

Exemple :

tableau initial :

53

23

89

13

97

5

18

46

après un premier parcours :

23

53

13

89

5

18

46

97

après un second parcours :

23

13

53

5

18

46

89

97

Algorithme

fonction triBulle(t InOut : tableau entier[0..n-1], n : entier)
    début
        j <- 0
        is_changed <- vrai
        tant que is_changed faire
            is_changed <- faux
            pour i de 0 à n-2-j faire
                si t[i]>t[i+1]
                    alors
                        tmp <- t[i]
                        t[i] <- t[i+1]
                        t[i+1] <- tmp
                        is_changed <- vrai
                fsi
            fpour
            j <- j+1
        ftant
    fin
    
    Lexique :
    - i : entier, variable d'it&eaucte;ration
    - j : entier, variable d'itération
    - is_changed : booléen, vrai si on peut continuer à permutter les valeurs
    - tmp : entier, variable temporaire utilisée pour les affectations
    - t : tableau entier[0..n-1], tableau à trier
    - n : entier, taille du tableau fourni en paramètre

Programme en Java

public class TrierTableau {
    private int[] tableau;
    public static int taille_tableau=8;

    public TrierTableau () {
        this.tableau = new int[this.taille_tableau];
    }

    public void initialiserTableau() {
        int valeur;
        for(int i=0; i<this.taille_tableau; i++)
        {
            System.out.println("Veuillez entrez la "+(i+1)+"e valeur :");
            valeur = Clavier.lireInt();
            this.tableau[i] = valeur;
        }
    }


    public void triBulle() {
        int j=0, tmp;
        boolean is_changed=true;
        while(is_changed)
        {
            is_changed = false;
            for(int i=0; i<=this.taille_tableau-2-j; i++)
            {
                if(this.tableau[i]>this.tableau[i+1])
                {
                    tmp = this.tableau[i];
                    this.tableau[i] = this.tableau[i+1];
                    this.tableau[i+1] = tmp;
                    is_changed = true;
                }
            }
            j++;
        }
    }

    public String toString() {
        String chaine="";
        for(int i=0; i<this.taille_tableau; i++)
        {
            chaine += this.tableau[i]+"\n";
        }
        return chaine;
    }

    public static void main(String[] args) {
        TrierTableau tabInt = new TrierTableau();
        tabInt.initialiserTableau();
        System.out.println("\n\nLe tableau avant le tri :");
        System.out.println(tabInt);
        tabInt.triBulle();
        System.out.println("\n\nLe tableau apres tri :");
        System.out.println(tabInt);
        System.exit(0);
    }
}

Programme en C

#include <stdio.h>

#define NBMAX 8
#define TRUE 1
#define FALSE 0


void afficherTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("t[%d] = %d\n", i, tab[i]);
	}
}


void remplirTableau(int tab[])
{
	int i;
	for(i=0; i<NBMAX; i++)
	{
		printf("Veuillez saisir la %deme valeur :\n", i+1);
		scanf("%d", &tab[i]);
	}
}


void triBulle(int tab[])
{
	int i, j=0, tmp, is_changed=TRUE;
	while(is_changed==TRUE)
	{
		is_changed=FALSE;
		for(i=0; i<=NBMAX-2-j; i++)
		{
			if(tab[i]>tab[i+1])
			{
				tmp=tab[i];
				tab[i]=tab[i+1];
				tab[i+1]=tmp;
				is_changed=TRUE;
			}
		}
		j++;
	}
}


void main(void)
{
	int tableau[NBMAX];
	remplirTableau(tableau);
	printf("\n");
	afficherTableau(tableau);
	printf("\n");
	triBulle(tableau);
	printf("\n");
	afficherTableau(tableau);
}

Pour conclure, en Java, il est tout à fait possible d'utiliser ces algorithmes de tri sans avoir à créer d'objet mais pour cela il vous faudra utiliser non plus des méthodes d'instance mais des méthodes de classe pour cela il vous suffira de modifier les en-têtes de celle-ci et bien sûr de les appeler de la manière suivante Nom_de_la_classe.Méthode_de_classe(paramètre(s)).

Algorithme de tri de tableauDe l'algorithme au Java & C

Tri par sélection du minimum

Algorithme

Programme en Java

Programme en C

Tri par sélection croisée

Algorithme

Programme en Java

Programme en C

Tri bulle

Algorithme

Programme en Java

Programme en C

Algorithme de tri de tableau
De l'algorithme au Java & C