[PDF] Tri par insertion [tr05] - Exercice

View - Download Tri par insertion [tr05] - Exercice

Previous PDF

Next PDF

Tri par insertion [tr05] - Exercice

Karine Zampieri, Stephane Riviere

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Telechargements { Utilitaires

2

2 Tri par insertion / pginsertion

4

2.1 Tri par insertion basique

4

2.2 Tri par insertion, version 2

6

2.3 Conclusion

9

3 References generales

9 Java - Tri par insertion (Solution)Mots-ClesAlgorithmes de tris et rangs, Tri par insertion

RequisAxiomatique imperative (sauf Fichiers)

Diculte• ◦ ◦(45 min)Objectif

Cet exercice realise le tri par insertion d'un tableau d'entiers. Dans le m^eme ordre d'idees, l'exercice @[Tri bulle et associes] realise le tri bulle et l'exercice @[Tri par selection] celui par selection. 1

Unisciel algoprog { Tri par insertion [tr05]2

1 Telechargements { Utilitaires

Cet exercice utilise les operations suivantes, toutes denies dans un bon nombre d'exer- cices de cet espace thematique : •FonctionsaisirNombreElements •ProcedureafficherTri •ProcedurealeatoireTri •ProcedurepermuterTab Elles ont ete regroupees dans une bibliotheque.Denitions Java final

int TMAX= ...; Fixez la constanteTMAX=50(nombre maximum d'elements).Telechargezle chier suivant et mettez-le dans votre dossier.

Java@[UtilsTR.java]Copiez/collezensuite les lignes suivantes : Les operations seront accessibles en notation

usuelle.Soitla fonctionsaisirNombreElements(nmax)qui renvoie le nombre d'elements, saisi par

l'utilisateur, entier compris dans[1..nmax]. Elle ache l'invite :Nombred "élémentsdans [1..[ nmax]]?

Java@[saisirNombreElements] (dans UtilsTR.java)Soitla procedureafficherTri(t,n,g,h)qui ache, a la queue-leu-leu separes par un espace

le tout entre crochet, lesnpremieres valeurs d'unITableaut , les indicesgethindiquant le sous-intervalle du tri et representes par une barre verticale. La barre de gauche est avantget celle de droite est apresh. Exemple :afficherTri(t,10,4,9) ==> [1 2 3 |4 5 6 7 8 9 |10]

Java@[acherTri] (dans UtilsTR.java)Soitla procedurealeatoireTri(t,n,vmax)H qui initialise lesnpremiers elements d'un

ITableau

t en utilisantvmaxcomme valeur maximale pour la fonction de generation d'un entier pseudo-aleatoire.

Java@[aleatoireTri] (dans UtilsTR.java)

Unisciel algoprog { Tri par insertion [tr05]3Soitla procedurepermuterTab(t,j,k)qui permute leselements d'indicejetkd'unITableau

t. Les indices sont supposes valides.

Java@[permuterTab] (dans UtilsTR.java)Remarque

Si la fonction et les procedures n'ont pas ete realisees, il vous est conseille de la(les) rediger dans l'exercice @[Utilitaires Tris et Rangs]. ...(suite page suivante)...

Unisciel algoprog { Tri par insertion [tr05]4

2 Tri par insertion / pginsertion

2.1 Tri par insertion basiquePrincipe du tri par insertion

Letri par insertiond'un tableaut[1..n]denelements consiste, pourjvariant de 1 an, a inserer l'elementt[j]dans le sous-tableau triet[1..j-1]de sorte que le tableau t [1.. j ]soit trie.Exemple (Avec achage des tableaux successifs)Nombred "élémentsdans [1..50]? 10

Tableau

initial [ 13 12 6 7 13 18 17 4 18 3 ] Tri par insertion basique [ 13|12 6 7 13 18 17 4 18 3 |] [ 12 13| 6 7 13 18 17 4 18 3 |] [ 6 12 13| 7 13 18 17 4 18 3 |] [ 6 7 12 13|13 18 17 4 18 3 |] [ 6 7 12 13 13|18 17 4 18 3 |] [ 6 7 12 13 13 18|17 4 18 3 |] [ 6 7 12 13 13 17 18| 4 18 3 |] [ 4 6 7 12 13 13 17 18|18 3 |] [ 4 6 7 12 13 13 17 18 18| 3 |] [ 3 4 6 7 12 13 13 17 18 18||]

Tableau

final [ 3 4 6 7 12 13 13 17 18 18 ]

Remarque

Le tri par insertion est similaire au tri du joueur de cartes qui insere les cartes une a une dans son jeu de maniere a ce qu'a tout instant le jeu soit trie.

Unisciel algoprog { Tri par insertion [tr05]5

Ecrivez une procedureinsererElementBasique(t,k)qui insere l'elementt[k]dans le sous- tableau triet[1..k-1],tetant unITableau. La procedure utilisera la procedurepermuterTab pour realiser l'echange de deux elements det.Solution simple

Soitjl'indice de boucle.

Sit[k]est le plus petit element det[1],...,t[k-1], la boucle ne doit pas provoquer un debordement vers la gauche du tableau avec la comparaison det[0]au minimum courant.

Il faut donc tester systematiquement sij>1.

Ecrivez une proceduretriInsertionBasique(t,n)qui eectue le tri par insertion denele- ments d'unTableaut .Validez vos procedures avec la solution.

Solution Java@[pginsertion.java]/**

Insere

l l ment t k dans t [0.. k -1] trie @param in out t un

ITableau

@param in k indice d insertion public static void insererElementBasique(int[]t ,intk){ booleanpermutation= true;intj= k ;while(j> 0 && permutation ){ if(t[j] UtilsTR permuterTab t j j - 1); j else permutation = false;}

Unisciel algoprog { Tri par insertion [tr05]6/**

Tri par insertion d un

ITableau

@param in out t un

ITableau

@param in n nombre d l ments public static void triInsertionBasique(int[]t ,intn){ for(intj= 1; j < n ; ++j){

UtilsTR

afficherTri t n j n insererElementBasique t j

UtilsTR

afficherTri t n n n Ecrivez un programme qui saisit le nombre d'elements, declare unITableau2 et l'initialise de facon aleatoire en prenant20pour valeur maximale puis eectue son tri et l'ache.Testez.

2.2 Tri par insertion, version 2Principe de la sentinelle

An d'eviter le debordement vers la gauche lors de l'insertion de l'elementt[k]dans le sous-tableau triet[1..k-1], une autre solution est de mettre une sentinelle ent[1], c.-a-d. un element dont on est certain qu'il va arr^eter la boucle. Il sut pour cela qu'il soit inferieur a tout element rencontre, ce qui est le cas si l'on recherche au prealable l'element minimum et qu'on le met a cette place. Ecrivez une fonctionindiceMinTab(t,n)qui calcule et renvoie l'indicede l'element conte- nant la plus petite valeur parmi lesnpremieres valeurs d'unITableaut . En cas d'ex-aequo, c'est l'indice le plus petit qui sera renvoye.Validez votre fonction avec la solution.

Solution Java@[UtilsTBOpers.java]/**

Indice

du minimum d un

ITableau

@param in t un

ITableau

@param in n nombre de valeurs dans [1.. TMAX @return l indice du minimum des n valeurs de t public static int indiceMinTab(finalint []t ,intn){ intimin= 0; intvmin= t [imin]; Unisciel algoprog { Tri par insertion [tr05]7for(intj= 1; j < n ; ++j){ if(t[j] l'echange de deux elements det.Copiez/collez la proceduretriInsertionBasiqueentriInsertion(t,n), puis modiez la pro-

cedure de sorte qu'elle recherche tout d'abord l'element minimum desnelements detet le place ent[1]an qu'il joue le r^ole de sentinelle puis eectue la procedure d'insertion a partir de l'element 2.Validez vos procedures avec la solution.

Solution Java@[pginsertion.java]/**

Ins re t k dans t [0.. k -1] trie l ment minimum en t [0] @param in out t un

ITableau

@param in k indice d insertion public static void insererElement(int[]t ,intk)

Unisciel algoprog { Tri par insertion [tr05]8{

intj= k ;while(t[j] UtilsTR permuterTab t j j - 1); j Tri par insertion d un

ITableau

@param in out t un

ITableau

@param in n nombre d l ments public static void triInsertion(int[]t ,intn){ intj0= indiceMinTab (t,n);UtilsTR.permuterTab(t,0,j0); for(intj= 1; j < n ; ++j){

UtilsTR

afficherTri t n j n insererElement t j

UtilsTR

afficherTri t n n n Modiez votre programme an qu'il eectue le tri par insertion (version 2).

Testez.

Validez votre programme avec la solution.

Solution Java@[pginsertion.java]publicstatic void main(String[]args ){

intnelems= UtilsTR .saisirNombreElements(TMAX);int[]tab = newint [TMAX];UtilsTR.aleatoireTri(tab,nelems,20);

System

out println

Tableau

initial

UtilsTR

afficherTri tab nelems ,0, nelems

System

out println Tri par insertion triInsertionBasique tab nelemsquotesdbs_dbs6.pdfusesText_12

[PDF] algorithme de tri par insertion pdf

[PDF] algorithme de tri par sélection

[PDF] algorithme de tri par selection en c

[PDF] algorithme de tri par selection java

[PDF] algorithme de tri par selection pdf

[PDF] algorithme de tri par selection recursive

[PDF] algorithme de tri pdf

[PDF] algorithme de tri rapide

[PDF] algorithme du plus court chemin

[PDF] algorithme du plus court chemin dans un graphe

[PDF] algorithme du plus court chemin java

[PDF] algorithme du plus court chemin python

[PDF] algorithme et langage c

[PDF] algorithme et programmation

[PDF] algorithme et programmation en language c