[PDF] Chapitre 1 – Méthodes de tri et de recherche dans les tableaux I

View - Download Chapitre 1 – Méthodes de tri et de recherche dans les tableaux I

Previous PDF

Next PDF

Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

Chapitre 1

Méthodes de tri et de recherche dans les tableaux Parmi les méthodes dites rusées connues en algorithmique se trouvent celles dédiées à la recherche de valeur et au tri des données.

Les méthodes de recherche

servent à vérifier l'existence (ou non) d'une valeur dans un ensemble de

données alors que différentes méthodes de tris ont été développées afin de traiter des données

posant le problème de leur classement (tri)

Les algorithmes proposés ont des performances différentes, en terme de temps d'exécution et en

terme d'espace mémoire requis pour leur exécution. Nous allons voir dans ce chapitre les principaux algorithmes de tri et de recherche de données proposés dans la littérature de l'algorithmique . Formulés en sous-algorithmes, ces méthodes sont

appliquées sur des données manipulées en structure "Tableau" bien que le principe reste le même

pour les autres structures supportant ces méthodes.

I- Méthodes de recherche

La recherche d'une valeur peut

être positive en renvoyant l'affirmation de la présence de la valeur parmi les données ou se terminer par un échec avec un message de présence négative.

I-1- Recherche séquentielle

Vérifier la présence d'une valeur X de type réel dans un tableau (déjà rempli) de N éléments Réel.

Idée : Comparer les valeurs du tableau à la valeur X recherchée en commençant par la première

valeur et en avançant case par case vers la fin du tableau. La boucle de parcours se terminant naturellement à la fin du tableau indique l'absence de la valeur recherchée alors que la fonction rend une valeur "vrai" si le parcours est interrompu.

Fonction Rech-Seq (T : Tab, X : Reel) : Booleen

Declaration

Variable

I : entire;

Debut I 1;

Tantque

I I +1

FinTantque

Si I > N Alors

Rech

Seq Faux

Sinon Rech

Seq Vrai

FinSi Fin ;

I-2- Recherche dichotomique

Vérifier la présence d'une valeur X de type réel dans un tableau (déjà rempli) de

N éléments Réel

triés en ordre croissant.

Idée : Les valeurs du tableau étant dans un ordre croissant la valeur est comparée à celle du milieu

du tableau.

Trois indices sont alors nécessaires à ce travail : l'indice du début du tableau, celui de la

fin du tableau et l'indice de son milieu qui est calculé selon les deux premiers.

Trois possibilités se

présentent

(1) Bingo ! on est très chanceux et la valeur du milieu est égale à la valeur X recherchée, le

travail s'arrête alors avec un "vrai" à renvoyer à l'algorithme appelant ; Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

(2) La valeur du milieu est supérieure à celle recherchée, et dans ce cas la valeur si elle existe ne

peut être que dans la 1

ère

moitié du tableau ; (3) La valeur du milieu lui est inférieure, et alors la recherche doit se poursuivre dans la 2

ème

moitié du tableau).

Dans le cas (2) et (3) l'opération de comparaison est répétée sur le tableau qui rétréci

(théoriquement en déplaçant les bornes du tableau et recalculant son milieu) jusqu'à ce qu'il ne

reste plus de cases à comparer et le travail s'arrête avec une réponse négative

Fonction R

Dicho (T : Tab, X : Reel) : Booleen ;

Declaration

Variable

Inf, Sup, Mil : entier ;

Debut

Inf 1;

Sup N ;

R-Dicho faux

Tantque Inf Sup Faire

Mil (Inf + Sup) Div 2 ;

Si T(Mil)

= X alors

R-Dicho vrai

Sinon

Si T(Mil) > X Alors

Sup Mil - 1

Sinon

Inf Mil +1

finSi FinSi

FinTantque

Fin ;

I-3- Palindrome

Un tableau est dit Palindrome si la lecture de droite à gauche donne la même suite de valeur que la

lecture de gauche à droite.

Idée : Utiliser deux indices l'un pour la borne inférieure et l'autre pour la borne supérieure. La

comparaison se fait alors entres les deux valeurs et conduit à faire avancer le 1 er indice et reculer le 2

ème

vers le milieu du tableau tant que les valeurs sont égales. Dans le cas contraire le travail est arrêté pour certifier que le tableau n'est pas un palindrome.

Fonction Palind

(T : Tab) : Booleen ;

Declaration

Variable

I, j : entier ;

Debut

I 1 ;

J N ;

Tantque (I < J) et (T(I) = T(J)) Faire

I I + 1 ;

J J - 1 ;

FinTantque ;

Si I < J Alors

Palind faux

Sinon

Palind vrai

FinSi Fin ; Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

II- Méthodes de Tri

Plusieurs méthodes de tri sont proposées, les plus connues sont dites par insertion, sélection, à

bulles, fusion, rapide, etc.

Note : Trier le tableau en ordre croissant ou décroissant ne change en aucune façon la méthode de

travail ; il suffit d'inverser la comparaison des valeurs dans les sous algorithmes suivants pour obtenir un tri dans l'autre sens. II -1- Tri par sélection Principe : On recherche le minimum dans la partie restante du tableau et on l'échange avec

l'élément qui suit la partie déjà triée. Après k placements les k plus petits éléments du tableau sont

déjà à leurs places définitives. Procedure tri-select (Var tab: tableau de N entier) ;

Declaration

Variable

I, J, K, X : entier ;

Début

Pour I 1 a N-1 Faire

J I;

Pour K J+1 à N faire

Si tab (K) < tab (J) Alors

J K; FinSi

FinPour

X tab (I);

tab (I) tab (J) tab (J) X; c.-à-d. que l'on a trouvé une valeur plus petite et que l'on garde sa position pour permuter */

FinPour

Fin; II -2- Tri par insertion (VOIR TD) Principe : à la i-ème étape on insère le i

ème

élément à son rang parmi les i-1 éléments précédents qui sont déjà triés entre eux.

Procedure

Tri_insertion (var T : Tableau de N entier) ;

Variable

i, j, echange : entier ;

Début

Pour i Allant de 2 à N faire

echange

ĸi) ; ĸ- 1 ;

Tantque (j 1) et( echange < T(j)) Faire

Debut

T(j + 1) ĸ(j) ; ĸ-1

Fin

FinTantque

T(j+1) ĸ

FinPour

Fin ; II -2- Tri à bulles (VOIR TD) Principe : on parcourt le tableau en effectuant un échange à chaque fois que l'on trouve deux éléments successifs qui ne sont pas dans le bon ordre. Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

Il existe plusieurs versions :

a- tri à bulles avec parcours du début à la fin avec 2 boucles Pour imbriquées; b- tri à bulles amélioré (on retient l'indice de la dernière permutation); c- tri " shaker » - deux parcours du début à la fin, et inversement; d - tri à peigne (combsort) qui rivalise avec les tris rapides.

Une version pour la variante a

Procedure

tri-bulles (Var tab : tableau de N entier);

Variable

I, J, X : entier;

Debut

Pour J 1 jusqu'à N-1 faire

Pour J N jusqu'à I+1 pas= -1 faire

Si Tab(J) < Tab(J-1] alors

X Tab(J) ;

Tab (J) Tab (J-1) ;

Tab (J-1) X

FinSi

FinPour

I I+1;

FinPour

Fin ;

Une version améliorée où le travail s'arrête lorsqu'il n'y a plus de permutation (variante b) :

procedure

Tri_Bulle (Var T : Tableau de N entier) ;

Variables

i, echange : entier ; permut : booleen ;

Début

Répeter

Pour i 1 à N-1 Faire

Si T(i) > T(i+1) alors

ĸT[i+1]

FinSi

FinPour

Jusqu'à

permut = faux Fin ;

Note : Le tri fusion et le tri rapide nécessitent des notions présentées dans le prochain chapitre

(récursivité) Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

Mme Zitouni vous propose les sous algorithmes suivants avec leurs exécutions : /*tri par insertion*/ Procedure Tri_insertion (var T : Tableau de N entier) ;

Variable i, j, X : entier ;

Début

Pour (i Allant de 2 à N) faire

X<- T(i) ;

J<-i-1 ;

T(j + 1) <-T(j);

j <-j-1 ;

FinTantque

T(j+1) <-X;

FinPour

Fin ; /*tri à bulle non optimisé*/ Procedure Tri_a_bulle_non_opt (var T : Tableau de N entier) ;

Variable i, j : entier ;

X: réel;

Début

Pour (i Allant de N-1 à 1 Pas=-1) Faire /*cette boucle gère les comparaisons à faire*/ Pour (j Allant de 1 à i) Faire /*cette boucle gère les

éléments à comparer*/

Si (T(j + 1)

X<-T(j) ;

T(j) <- T(j+1);

T(j+1)<-X ;

FinPour

FinPour

Fin ;

Un exemple de déroulement de : T=7 5 8 3 2.

Un exemple de déroulement de : T=9 8 5 2 1.

I=2 7 5 8 3 2 5 7 8 3 2

I=3 5 7 8 3 2 5 7 8 3 2

I=4 5 7 8 3 2 3 5 7 8 2

I=5 3 5 7 8 2 2 3 5 7 8

I=4 9 8 5 2 1 8 5 2 1 9

I=3 8 5 2 1 9 5 2 1 8 9

I=2 5 2 1 8 9 2 1 5 8 9

I=1 2 1 5 8 9 1 2 5 8 9

Module : Programmation et structures de données. MI- CNE 2- 2015-2016

Chapitre 1 : Techniques rusées

Remarque :

Si on exécute la procédure Tri_a_bulle_non_opt pour le tableau trié T= 1 2 5 8 9 on passera par les même itérations

de l'exécution précédente pour cela il y on a plusieurs version qui apportent des améliorations à cette procédure.

/*tri à bulle optimisé version1*/ Procedure Tri_a_bulle _opt1 (var T : Tableau de N entier) ;

Variable i, j, Trie : entier ;

X: réel;

Début

Pour (i Allant de N-1 à 1 Pas=-1) Faire

Trie<-0 ;

Pour (j Allant de 1 à i) Faire

Si (T(j + 1)

X<-T(j) ;

T(j) <- T(j+1);

T(j+1)<-X ;

Sinon

Trie<-Trie+1 ;

Finsi

FinPour

Si (Trie=i ) alors

i <-1 ;

FinPour

Fin ; /*tri à bulle optimisé version2*/ Procedure Tri_a_bulle _opt2 (var T : Tableau de N entier) ;

Variable i, j: entier ;

X: réel;

B : booléen ;

quotesdbs_dbs12.pdfusesText_18

[PDF] mode d'emploi fitbit flex 2

[PDF] diagramme de bloc interne definition

[PDF] diagramme ibd

[PDF] diagramme sysml definition

[PDF] comment faire un diagramme sysml

[PDF] diagramme d'exigence definition

[PDF] diagramme bdd

[PDF] sysml diagramme

[PDF] diagramme de définition de bloc

[PDF] transmission double nom de famille

[PDF] choix du nom de famille mariage

[PDF] ajouter nom de famille grand mere

[PDF] transmission nom d'usage

[PDF] double nom de famille mariage

[PDF] nom de famille composé trait d'union