Les Tris Des Tableaux

LES TRIS DES TABLEAUX 1. LE TRI A BULLE : Le principe du tri à bulle consiste à tester les éléments consécutifs d’un tableau et de les permuter si l’élément occupant la Xième place est plus grand que l’élément qui le suit. 2.LE TRI PAR PERMUTATION C’est le tri du jeu de cartes. • • •

On parcourt le tableau jusqu'à ce que l'on trouve un élément plus petit que le précédent, donc mal placé. On prend cet élément et on le range à sa place dans le tableau puis on continue la lecture. On s'arrête à la fin du tableau.

Tableau

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Tour 1

52

10

1

25

62

3

8

55

3

23

Tour 2

10

52

1

25

62

3

8

55

3

23

Tour 3

1

10

52

25

62

3

8

55

3

23

Tour 4

1

10

25

52

62

3

8

55

3

23

Tour 5

1

3

10

25

52

62

8

55

3

23

Tour 6

1

3

8

10

25

52

62

55

3

23

Tour 7

1

3

8

10

25

52

55

62

3

23

Tour 8

1

3

3

8

10

25

52

55

62

23

Tour 9

1

3

3

8

10

23

25

52

55

62

Algorithme Pour i allant de 2 a (fin de tableau) Si tableau (i) > tableau (i - 1)alors J = i faire X = tableau(j - 1) tableau (j - 1) = tableau(j) tableau(j) = X J = (j - 1) Jusqu'à (j = 1) ou (tableau (j - 1) > tableau (j)) Fin de si Fin de pour

1/11

3.LE TRI PAR COMPTAGE : Le tri par comptage consiste pour chaque élément du tableau à compter combien d'éléments sont plus petit que lui. Grâce à ce chiffre on connait sa position dans le tableau résultat. Principe tableau

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 52

10

1

25

62

3

8

55

3

23

Nbr + petit

7

4

0

6

9

1

3

8

1

5

Position

8

5

1

7

10

2

4

9

3

6

Algorithme Pour i allant de 1 a (fin de tableau) Res(i) = 0 Nb(i) = 0 'calcule des compteurs Pour j allant de 1 a (fin de tableau) Si tableau(j) < tableau(i) alors Nb(i) = nb(i) + 1 Fin de si Fin de pour Fin de pour 'Positionnement Pour i allant de 1 a (fin de tableau) J = nb(i) Tant que res(j) <> 0 'cas des doubles J = j + 1 Fin de tant que Res(j) = tableau(i) Fin de pour 4.LE TRI PAR SELECTION Le principe du tri par sélection/échange (ou tri par extraction) est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit élément du vecteur pour le mettre en second, etc... 5.LE TRI PAR INSERTION : Le principe du tri par insertion est d'insérer à la n-ième itération le n-ième élément à la bonne place.

2/11

TRI A BULLE class ApplicationTribulle //VARIANTE 1 { static int[] table = new int[20] ; // le tableau à trier en attribut static int n = table.length-1; static void Impression ( ) { // Affichage du tableau for ( int i = 1; i<=n; i++) System.out.print(table[i]+" , "); System.out.println(); } static void Initialisation ( ) { // remplissage aléatoire du tableau for ( int i = 1; i<=n; i++) table[i] = (int)(Math.random()*100); } static void Tribulle ( ) { int n = table.length-1; int i; boolean ok; do { ok=false; for(i=1;i<=n;i++) if (table[i-1]>table[i]) { int temp = table[i-1]; table[i-1] = table[i]; table[i]= temp; ok=true; } } while(ok); } public static void main(String[ ] args) { Initialisation ( ); System.out.println("Tableau initial :"); Impression ( ); Tribulle ( ); System.out.println("Tableau une fois trié :"); Impression ( ); } } /*ALGOrithme FAIRE inversion <-- FAUX 3/11

POUR i ALLANT DE 1 A n FAIRE SI (TAB(i) > TAB(i+1)) ALORS Tampon <-- TAB(i); TAB(i) <-- TAB(i-1); TAB(i-1) <-- Tampon inversion <-- VRAI FSI FinPour JUSQUA (inversion = FAUX); */ VARIANTE 2 : class ApplicationTriBulle { static int[] table = new int[10] ; // le tableau à trier en attribut static void TriBulle ( ) { int n = table.length-1; for ( int i = n; i>=1; i--) for ( int j = 2; j<=i; j++) if (table[j-1] > table[j]) { int temp = table[j-1]; table[j-1] = table[j]; table[j] = temp; } } static void Impression ( ) { // Affichage du tableau int n = table.length-1; for ( int i = 1; i<=n; i++) System.out.print(table[i]+" , "); System.out.println(); } static void Initialisation ( ) { // remplissage aléatoire du tableau int n = table.length-1; for ( int i = 1; i<=n; i++) table[i] = (int)(Math.random()*100); } public static void main(String[ ] args) { Initialisation ( ); System.out.println("Tableau initial :"); Impression ( ); TriBulle ( ); System.out.println("Tableau une fois trié :"); Impression ( ); } } /* Algorithme Tribulle pour i de n à 1 faire 4/11

pour j de 2 à i faire si table[j-1]>table[j] alors temp=table[j-1]; table[j-1]=table[j] table[j]=temp Fsi Fpour */ import java.util.*; class ApplicationTribulle { static int[] table = new int[20] ; // le tableau à trier en attribut static int n = table.length-1; static void Impression ( ) { // Affichage du tableau for ( int i = 1; i<=n; i++) System.out.print(table[i]+" , "); System.out.println(); } static void Initialisation ( ) { // remplissage aléatoire du tableau for ( int i = 1; i<=n; i++) table[i] = (int)(Math.random()*100); } static void Tribulle ( ) {

Arrays.sort(table);

} public static void main(String[ ] args) { Initialisation ( ); System.out.println("Tableau initial :"); Impression ( ); Tribulle ( ); System.out.println("Tableau une fois trié :"); Impression ( ); } } class ApplicationTriSelection//variante1 { static int[] table = new int[20] ; // le tableau à trier en attribut static void Impression ( ) { // Affichage du tableau int n = table.length-1; for ( int i = 1; i<=n; i++) System.out.print(table[i]+" , "); System.out.println(); 5/11

} static void Initialisation ( ) { // remplissage aléatoire du tableau int n = table.length-1; for ( int i = 1; i<=n; i++) table[i] = (int)(Math.random()*100); } static void TriSelect ( ) { int n = table.length-1; for ( int i = 1; i <= n-1; i++) { // recommence une sous-suite int m = i; // élément frontière ai = table[ i ] for ( int j = i+1; j <= n; j++) // (ai+1, a2, ... , an) if (table[ j ] < table[ m ]) // aj = nouveau minimum partiel m = j ; // indice mémorisé int temp = table[ m ]; table[ m ] = table[ i ]; table[ i ]= temp; } } public static void main(String[ ] args) { Initialisation ( ); System.out.println("Tableau initial :"); Impression ( ); TriSelect ( ); System.out.println("Tableau une fois trié :"); Impression ( ); } } /*ALGORITHME pour i de 1 jusquà n-1 faire // recommence une sous-suite m i ; // i est l'indice de l'lment frontire ai = Tab[ i ] pour j de i+1 jusquà n faire// (ai+1 , ai+2 , ... , an ) si Tab[ j ] < Tab[ m ] alors // aj est le nouveau minimum partiel m j ; // indice mmoris Fsi fpour; temp Tab[ m ] ; Tab[ m ] Tab[ i ] ; Tab[ i ] temp //on change les positions de ai et de aj fpour*/

class Triselect// variante 2 { public static void main(String args[]) { int [] T = {52,10,1,25,62,30,8,55,3,23}; 6/11

int i,j,N,petit,position; N=T.length; for (i=0;ii;j--) T[j] = T[j-1]; T[i] = petit; }

System.out.println("Tableau trié: "); for (i=0;i
7/11

class ApplicationTriInsert { // le tableau à trier: static int[] table = new int[10] ; /*-------------------------------------------------------------------Dans la cellule de rang 0 se trouve une sentinelle chargée d'éviter de tester dans la boucle tantque .. faire si l'indice j n'est pas inférieur à 1, elle aura une valeur inférieure à toute valeur possible de la liste -------------------------------------------------------------------*/ static void Impression ( ) { // Affichage du tableau int n = table.length-1; for ( int i = 0; i<=n; i++) System.out.print(table[i]+" , "); System.out.println(); } static void Initialisation ( ) { // remplissage aléatoire du tableau int n = table.length-1; for ( int i = 1; i<=n; i++) table[i] = (int)(Math.random()*100); //sentinelle à l'indice 0 : table[0] = -Integer.MAX_VALUE; } public static void main(String[ ] args) { Initialisation ( ); System.out.println("Tableau initial :"); Impression ( ); TriInsert ( ); System.out.println("Tableau une fois trié :"); Impression ( ); } static void TriInsert ( ) { // sous-programme de Tri par insertion : int n = table.length-1; for ( int i = 2; i <= n; i++) { int v = table[i]; int j = i; while (table[ j-1 ] > v) {// travail sur la partie déjà triée (a1, a2, ... , ai) table[ j ] = table[ j-1 ]; // on décale l'élément j--; // on passe au rang précédent } table[ j ] = v ; //on recopie ai dans la place libérée } } }

8/11

/*AGORITHME { dans la cellule de rang 0 se trouve une sentinelle chargée d'éviter de tester dans la boucle tantque .. faire si l'indice j n'est pas inférieur à 1, elle aura une valeur inférieure à toute valeur possible de la liste pour i de2 jusquà n faire// la partie non encore triée (ai , ai+1 , ... , an ) v =Tab[ i ] ; // l'lment frontire : ai j= i ; // le rang de l'lment frontire Tantque Tab[ j-1 ] > v faire // on travaille sur la partie déjà triée (a1 , a2 , ... , ai) Tab[ j ] = Tab[ j-1 ]; // on dcale l'lment j = j-1; on passe au rang prcdent FinTant ; Tab[ j ]= fpour*/

v;//on recopie ai dans la place libérée

class TriPermut { /* ALGORITHME POUR i ALLANT DE 1 A 9 FAIRE SI (TAB(i+1) < TAB(i)) ALORS abouger <-- TAB(i+1); j <-- 1; TantQue ((j < i) ET (TAB(j) < TAB(i+1))) Faire j <-- j+1 FTQ POUR k ALLANT DE i+1 A j+1 PAS -1 Faire TAB(k) <-- TAB(k-1) FinPour TAB(j) <-- abouger; FSI FinPour */ public static void main(String args[]) throws IOException { int [] T = {52,10,1,25,62,3,8,55,3,23}; int i,j,k,N,abouger; N=T.length; 9/11

for (i=0;i
}

for (k=i+1;k>j;k--) T[k] = T[k-1]; T[j] = abouger;

System.out.println("Tableau trié: "); for (i=0;i
import java.io.*; class triComptage { /* Voir fichier ALGO.DOC POUR i ALLANT DE 1 A 10 FAIRE RES( i ) <-- 0 NB( i ) <-- 0 * calcul des compteurs * POUR j ALLANT DE 1 A 10 FAIRE SI TAB( j ) < TAB( i ) ALORS 1 FSI FinPour FinPour POUR i ALLANT DE 1 A 10 FAIRE j <-- NB( i ) TantQue RES( j ) <> 0 doubles * Faire j <-- j+1 FTQ RES( j ) <-- TAB( i ) FinPour */ {

NB( i ) <-- NB( i ) +

* pour le cas des

public static void main(String args[]) throws IOException int [] T = {52,10,1,25,62,3,8,55,3,23}; 10/11

int i,j,N; N=T.length; int [] RES = new int[N]; int [] NB = new int[N]; for (i=0;i
} }

System.out.println("Tableau trié: "); for (i=0;i
11/11