M´ethodes de programmation Algorithmes de recherche, tri et s´election

8/21/2019 M´ethodes de programmation Algorithmes de recherche, tri et s´election

http://slidepdf.com/reader/full/methodes-de-programmation-algorithmes-de-recherche-tri-et-selection 1/117

Methodes de programmationAlgorithmes de recherche,

tri et selection

M. MATHIEU

[email protected]

octobre-novembre 2004



. , ,

Selection. Recherche. Tri

Hypotheses de travail :

Ensemble fini E . E sous-ensemble d’un ensemble

de base X (E ⊂ X ).

Ensemble X muni d’une relation d’ordre totale

.

E = N .E = {x1, x2, . . . xN }

Problemes :

Recherche

”Verifier l’existence d’un element donne”

Si x ∈ X , trouver si x ∈ E . (trouver i tel que

x = xi)

Selection”Trouver les elements extremes de l’ensemble”

Trouver x = min(E ) et/ou y = max(E )

cM.Mathieu Generalites



. , ,

Tri

”Ordonner en ordre croissant (ou decroissant)

les elements d’un ensemble”

Trouver une permutation σ de l’ensemble

{1, 2, . . . , N }telle que ∀i < j : xσ(i) xσ( j).

Afficher les elements de E dans l’ordre induitpar σ :

xσ(1) xσ(2) . . . xσ(N )




. , ,

Schema d’etude :

– Complexite theorique

– Solutions

– (Nouvelles) Structures de donnees et leurs

solutions

– (Solutions pour cas particuliers)

– Complexite pour chaque solution




. , ,

Structures de donnees :

Structures de donnes connues : Vecteur et

liste chaınee (ordonnes ou pas)

Cout de mise en place et de mise a jour :

– insertion

– suppression

– (recherche)

Nouvelles structures : tas, arbres ...




. , ,

Recherche

1. Problematique et complexite theorique

2. Recherche sequentielle dans vecteurs et listes

non-ordonnes / ordonnes

3. Recherche dichotomique

Recherche par interpollation

4. Arbres binaires de recherche

5. Arbres equilibres

6. Tables de hachage

cM.Mathieu Recherche



. , ,

Probleme : Soient E ⊂ X une ensemble de cles,

muni d’un ordre total et x ∈ X , verifier si

x ∈ E .

Verifier si un element se trouve dans un en-

semble donnee. Si oui, indiquer cet element, si-non indiquer un diagnostic d’erreur et/ou in-

diquer le plus petit element qui le depasse ou

autres informations ...

Cle multiple : une valeur qui se trouve plus

d’une fois dans l’ensemble E . Si E admet de cles

multiples, en cas de recherche sur une telle cle

trouver la premiere / derniere / une quelconque

apparition de cette cle.

D’apres Knuth [4] la recherche prend la plu-part du temps de la plupart des programmes ...




. , ,

Structures de donnees

Dictionnaire : structure de donnees qui per-

met :

– insertion

– supression

– recherche

Exemples : liste chainee, vecteur non-ordonne /

ordonne, arbre de recherche, arbre rouge et noir,

AVL, B-arbre, table de hachage.




. , ,

Complexite

Les operations qui interviennent lors d’une re-

cherche sont essentiellement des comparaisons.

Hypothese : On ne fait que des comparaisons

entre x et xi ∈ E . Le resultat d’une comparaison

est : =, ≺ ou .

Exemple : L’arbre des comparaisons pour l’en-

semble {x1, x2}.

x1 : x

OUIx2 : x

OUI OUINON NONNONNON

x2 : x

=

= =< <> >

><




. , ,

Remarque 1 : Si v nœud interieur d’un arbre

de comparaisons, alors degre(v) = 4 ou 3 pour

la racine ; sinon, degre(v) = 1. Chaque nœudinterieur a comme descendant au plus 2 autres

nœuds interieurs.

Remarque 2 : Si A arbre de comparaisons, alors

A a au moins N nœuds interieurs.

Theoreme : La recherche d’un element dans un

ensemble de taille N , en effectuant que des com-

paraisons, se fait en executant au moins log N comparaisons.

Preuve : Si A est l’arbre de comparaisons d’une

telle recherche, le nombre de comparaisons estdonnee par la hauteur de l’arbre.

Compte tenu de remarques faites, soit k la hau-

teur minimale d’un arbre de comparison ayant

au moins N nœuds interieurs. Alors :

1 + 2 + . . . + 2k−1 < N ≤ 1 + 2 + . . . + 2k−1 + 2k

2k − 1 < N ≤ 2k+1 − 1

Donc k = log N .




. , ,

Recherche sequentielle

Principe : Parcourir les elements de l’ensembleE l’un apres l’autre en verifiant l’egalite.

Pour tout i de 1 a N comparer x et xi

Complexite en O(N)

Nombre de comparaisons : minimum 1 et maxi-

mum N, si x ∈ E . Si x /∈ E , entre 1 ou N + 1

comparaisons.




. , ,

Recherche sequentielle dans un tableau non-ordonne

int r_seq_vect_non_ord(int v[], int N, int x){

int i;for (i = 0; i < N; i++)

if (v[i] == x) return i;return -1;

}

Nombre moyen de comparaisons :

M = p1 + 2 p2 + . . . + NpN + (N + 1)q , ou

pi = probabilite x = xi, i = 1, N

q = probabilite x /∈

E .N

i=1

pi + q = 1

Remarque : La methode de recherche est plus

efficace, si les elements les plus frequents sont

places vers le debut de la structure.

Si p1 = p2 = . . . = pN , alors

M = p1N (N + 1)

2 + q(N + 1)




. , ,

si q = 0, M = N + 12

si q = 1

2, alors M =

3(N + 1)

4

Operations avec un tableau non-ordonne :

– insertion : O(1)

– suppression : O(1) apres une rechercheint insert_vect_non_ord(

int v[], int *taille, int valeur){

v[*taille] = valeur;++*taille;

return;}

int supp_vect_non_ord(int v[], int *taille, int position)

{v[position] = v[*taille-1];

--*taille;return;

}




. , ,

Recherche sequentielle dans une liste non-ordonnee

liste recherche_seq_liste_non_ord(liste tete, int valeur)

{liste aux;

aux = tete;while ((aux != NULL) && (aux->cle != valeur)){

aux = aux->next;}return aux;

}

Operations avec une liste non-ordonnee :

– recherche : O(N )

– insertion : O(1)

– suppression : O(N ), i.e. O(1) apres une re-

cherche.




. , ,

int insert_liste_non_ord(liste *tete, int valeur)

{liste aux;

aux = (liste)malloc(sizeof(struct element));aux->cle = valeur;aux->next = *tete;*tete = aux;

}

int supp_elt_liste_non_ord(liste *tete, int valeur)

{ liste aux, avant;

if (*tete == NULL)return FALSE;

if ((*tete)->cle == valeur){

*tete = (*tete)->next;return TRUE;

}

else{

avant = *tete;aux = (*tete)->next;while((aux != NULL)

&& (aux->cle != valeur)){

avant = aux;aux = aux->next;

}if (aux == NULL)

return FALSE;else

avant->next = aux->next;}

}




. , ,

Recherche sequentielle dans un tableau or-donne

int recherche_seq_vecteur_ord(int v[], int N, int valeur)

{int i;for (i = 0; (i < N) && (v[i] <= valeur); i++)

if (v[i] == valeur) return i;return -1;

}

Complexite moyenne :

M =N

i=1

ipi +N

i=0

(i + 1)qi ou :

pi = probabilite x = xi, i = 1, N

q0 = probabilite x < x1,

qN = probabilite x > xN

qi = probabilite xi < x < xi+1, i = 1, N

−1

N i=1

pi +N

i=0

qi = 1




. , ,

Sous l’hypothese :

p1 = p2 = . . . = pN et q0 = q1 = . . . = qN

le nombre moyen de comparaisons est :

M = p1N (N + 1)

2

+ q0(N + 1)(N + 2)

2

Si P (x ∈ E ) = 1, alors M = N + 1

2 .

Si P (x ∈ E ) = 1

2, alors M =

2N + 3

4 (resultat

legerement meilleur que pour un vecteur non-ordonne).

Operations sur tableaux ordonnes :

– recherche sequentielle O(N )

– suppression, insertion : O(N )

Remarque : le minimum et le maximum se trouvent

sur la premiere, respectivement, la derniere po-

sition du tableau.




. , ,

Recherche sequentielle dans une liste or-donnee

liste recherche_seq_liste_ord(liste tete, int valeur)

{liste aux;

aux = tete;while ((aux != NULL) && (aux->cle < valeur)){

aux = aux->next;}

if ((aux != NULL) && (aux->cle == valeur))return aux;

elsereturn NULL;

}

Recherche, insertion, suppression en temps

lineaire (O(N )).




. , ,

int supp_elt_liste_ord(

liste *tete, int valeur){

liste aux, avant;

if (*tete == NULL)return FALSE;

if ((*tete)->cle == valeur){

*tete = (*tete)->next;return TRUE;

}else{

avant = *tete;aux = (*tete)->next;while((aux != NULL) && (aux->cle < valeur))

{avant = aux;aux = aux->next;

}if ((aux == NULL) || (aux->cle > valeur))

return FALSE;else{

avant->next = aux->next;}

}}




. , ,

int insert_liste_ord(

liste *tete, int valeur){

liste aux;liste temp, prev;

aux = (liste)malloc(sizeof(struct element));aux->cle = valeur;

if (valeur <= (*tete)->cle){

aux->next = *tete;*tete = aux;return;

}else{

prev = *tete;temp = (*tete)->next;while ((temp != NULL) && (valeur > temp->cle)){

prev = temp;temp = temp->next;

}prev->next = aux;

aux->next = temp;}return;

}




. , ,

Recherche dichotomique

Applicable a des vecteurs ordonnes.

Remarque preliminaire : Soient T un vecteur or-donne et x un element qui se trouve entre leposition g et d du vecteur (g < d). Soit j indiceentre g et d.Si x > T [ j], alors x se trouvent entre j + 1 et d.Si x < T [ j], alors x se trouvent entre g et j

−1.

(methode ”diviser pour regner”)

Le choix le plus simple de l’indice j (positionpivot) est la position mediane entre g et d :

j = m =g + d

2

L’algorithme de recherche dichotomique s’ecrit :

si g > d, return ECHEC

m

← g + d

2

compare x et T [m] :x = T [m], return mx < T [m], recherche entre g et m − 1x > T [m], recherche entre m + 1 et d




. , ,

Forme recursive :

int recherche_dich(int T[], int g, int d, int x)

{int m;if (g > d) return -1;

m = (g + d) / 2;if (T[m] < x)

return recherche_dich(T, m+1, d, x);if (T[m] == x)

return m;else

return recherche_dich(T, g, m-1, x);}

Forme sequentielle :

int recherche_dich_bis(

int T[], int g, int d, int x){int m;while (g <= d){

m = (g + d) / 2;if (T[m] == x)

return m;

if (T[m] < x)g = m + 1;else

d = m - 1;}return -1;

}




. , ,

Theoreme : La recherche dichotomique necessite

maximum log2 N + 1 comparaisons, autant en

cas de succes qu’en cas d’echec.

Preuve : Apres chaque comparaison, s’il n’y a

pas d’egalite, l’espace de recherche est divise

par 2.

Donc apres k comparaisons l’espace de recherche

est de taille N

2k.

La recherche s’arete en cas de succes ousi

N

2k < 1.

Donc on effectue au plus K + 1 comparaisons,

ou K = log2 N .

La complexite de la recherche dichotomique est

O(log N ), car les operations adjacentes realisees

a chaque comparaison (calcul de la position median

se font en temps constant.

Remarque 1 : L’algorithme ennonce de recherche

dichotomique s’adapte facilement pour des ta-

bleaux avec des cles multiples afin de choisir

soit la premiere occurence de cette cle, soit la

derniere.

Remarque 2 : Pour des structures a cles mul-

tiples la complexite de l’algorithme reste inchangee.cM.Mathieu Recherche



. , ,

La recherche dichotomique est implantee au ni-

veau de la librairie stdlib. Sa declaration est la

suivante au niveau de stdlib.h :

void *bsearch(const void *key,const void *base, size_t nel, size_t size,int (*compar)(const void *, const void *));

Exemple d’utilisation pour la recherche dans unvecteur d’entiers :

static int comp(void *e1, void *e2){

int *p1, *p2;p1= e1;p2 = e2;return (p1 <= p2);

}

int T[300];int N;int val;

int main(){

int *p;.....

p = bsearch(&val, T, N, sizeof(int), comp);if (p== NULL)

printf(" Echec \n");else

printf(" ... %d... ", *p);....

}




. , ,

Recherche interpolee

Applicable aux vecteurs ordonnes, de preference

ayant les elements uniformement distribues.

Principe : Prendre comme position m pivot de

comparaison la position estimee de x dans le

tableau.

g m d

T[g]

x

T[d]

L’indice m serait donne par une formule de type :

m =

x − T [g]

T [d] − T [g](d − g) + g

sous les conditions T [g] = T [d] et T [g] ≤ x ≤T [d].cM.Mathieu Recherche



. , ,

int recherche_interpolee(int T[], int g, int d, int x)

{int m;

while (g <= d){

if (x < T[g])return -1;

if (x > T[d])return -1;

if (T[g] == T[d])return g;

m = 1.0*(x-T[g])/(T[d]-T[g])*(d-g)+g;if (T[m] == x)

return m;if (T[m] < x)

g = m + 1;else

d = m - 1;}return -1;

}

La condition d’uniformite pour la distribution

des elements du tableau est tres forte et la re-cherche interpolee peut donner de tres mauvais

resultats en son absence (exemple : la recherche

de 12 parmi 1, 2, 3, 4, 5, 6, 1000, 1001, 1002,

1003, 1004, 1005 demande 6 comparaisons).




. , ,

Une combinaison de la recherche dichotomiqueclassique et de la recherche par interpolationpeut etre proposee :

int recherche_interp_dich(int T[], int g, int d, int x)

{int m, me;while (g <= d){

if (x < T[g])

return -1;if (x > T[d])return -1;

if (T[g] == T[d])return g;

m = 1.0*(x-T[g])/(T[d]-T[g])*(d-g)+g;if (T[m] == x)

return m; me = (g + d) / 2;if (T[m] < x)

if ((T[me] < x ) && (m < me))g = m e + 1 ;

elseg = m + 1 ;

elseif ((T[me] > x) && (me < m))

d = me -1;else

d = m - 1 ;}return -1;

}




. , ,

Analyse de complexite

Remarque 1 : Les calculs faits a chaque iteration

sont toujours en temps constant (tant pour la

version initiale que pour la version corrigee).

Remarque 2 : La version initiale execute au plus

N iterations.

La version corrige necessite au plus log2 N

iterations.

Theroreme : La recherche par interpolation necess

dans le cas ou les valeurs sont uniformement dis-

tribuees un temps en O(log2 log2 N ).

Preuve tres technique ! ! ! Voir une ebauche dans :

G.N. GONNET ”Handbook of Algorithms and Data Struc-

tures”, Adison-Wesley, 1984, page 34

Ce resultat ne contredit pas la complexite

theorique de la recherche en O(log N ), car l’in-

terpolation est basee aussi sur un calcul des va-

leurs recherchees.




. , ,

Arbres de recherche

Definition : Structures de donnees organisees

en arborescences dont les nœuds contiennentune ou plusieurs cles et qui permettent de

rechercher, inserer ou supprimmer une cle

dans un temps raisonable.

Exemples : arbres binaires de recherche, arbres

noir et rouge, AVL, B-arbres (2-3-4 arbres).




. , ,

Arbres binaires de recherche (ABR)

Definition : Un ABR est arborescence binaire

dont chaque nœud x contient une cle cle(x) et

pour tout nœud les proprietes suivantes sont sa-

tisfaites :

– si y nœud se trouvant dans le sous-arbre

gauche de x, alors cle(y) ≤ cle(x)

– si y nœud se trouvant dans le sous-arbre

droit de x, alors cle(y) > cle(x)

SG SD

x




. , ,

Exemple :

21

13 28

18

15 20101

7 25

9 12




. , ,

Remarques :

1. Un parcours dans l’ordre

”sous-arbre gauche, racine, sous-arbre droit”

(forme in-fixe) permet d’obtenir les cles triees.

2. L’element le plus a gauche est l’element le

plus petit de l’ensemble des cles.

L’element le plus a droite est l’element le

plus grand.3. La recherche d’une cle se fait au long du

chemin entre la racine et le nœud qui la

contient, si la cle se trouve dans l’ABR, ou

vers la plus proche valeur, sinon.

/* definition du type */

struct noeud

{

int cle;

int info;

struct noeud* gauche;struct noeud* droit;

};

typedef struct noeud* ABR;




. , ,

/* parcours infixe */

void affiche_infixe_arbre(ABR racine){if (racine == NULL)

return;affiche_infixe_arbre(racine->gauche);printf(" %d ", racine->cle);affiche_infixe_arbre(racine->droit);return;

}

ABR max_ABR(ABR racine){

ABR tmp;if (racine == NULL) return NULL;tmp = racine;while (tmp->droit != NULL)

tmp = tmp->droit;return tmp;}

ABR min_ABR(ABR racine){

ABR tmp;if (racine == NULL) return NULL;tmp = racine;while (tmp->gauche != NULL)

tmp = tmp->gauche;return tmp;

}




. , ,

/* recherche dans un ABR */ABR recherche_ABR(ABR racine, int valeur){

ABR tmp;tmp = racine;

while (tmp != NULL)

{if (tmp->cle == valeur) return tmp;if (valeur < tmp->cle)

tmp = tmp->gauche;else

tmp = tmp->droit;}return NULL;

}

/* creation d’un ABR avec un seul noeud */void cree_racine(ABR *racine, int valeur){

*racine = (ABR)malloc(sizeof(struct noeud));(*racine)->cle = valeur;(*racine)->gauche = NULL;

(*racine)->droit = NULL;}




. , ,

Operations avec les ABR

– creation d’une racine – O(1).

– recherche – O(h), h etant la profondeur de

l’ABR (la longueur maximale d’un chemin

entre la racine et une feuille).

– selection min/max – O(h)

– suppression min/max – O(h)

– ajout dans une feuille O(h), car h comparai-sons maximum pour detreminer l’endroit et

un temps constant pour la creation meme.

– suppression – O(h), car 4 cas sont pos-

sibles :




. , ,

– ajout dans la racine – O(h), car on avantdoit partager l’ABR en 2 (operation de cou-

pure).

< a

X

>a

SG SD

x




. , ,

void insert_feuille_ABR(ABR *racine, int valeur){

if (*racine == NULL) cree_racine(racine, valeur);else

if ((*racine)->cle >= valeur)insert_feuille_ABR(&((*racine)->gauche), valeur);

else

insert_feuille_ABR(&((*racine)->droit), valeur);}

void enleve_max_ABR(ABR *racine, ABR *pt_max){

if (*racine == NULL){

*pt_max = NULL;

return;}if ((*racine)->droit == NULL){

*pt_max = *racine;*racine = (*racine)->gauche;return;

}else

enleve_max_ABR(&((*racine)->droit), pt_max);}




. , ,

void supprime_ABR(ABR *racine, int valeur){

ABR tmp;if (*racine == NULL)

return;

if (valeur < (*racine)->cle){

supprime_ABR(&((*racine)->gauche), valeur);return;

}if (valeur > (*racine)->cle){

supprime_ABR(&((*racine)->droit), valeur);return;}/* (*racine)->cle == valeur */if ((*racine)->gauche == NULL){

tmp = *racine;*racine = (*racine)->droit;free(tmp);return;

}if ((*racine)->droit == NULL){

tmp = *racine;*racine = (*racine)->gauche;free(tmp);return;

}else{

enleve_max_ABR(&((*racine)->gauche), &tmp);tmp->gauche = (*racine)->gauche;tmp->droit = (*racine)->droit;free(*racine);*racine = tmp;

}}




. , ,

void coupure_ABR(ABR racine, int valeur, ABR *ag, ABR *ad)

{if (racine == NULL){

*ag = NULL;*ad = NULL;return;

}if (valeur <= racine->cle){

*ad = racine;

coupure_ABR(racine->gauche, valeur, ag, &((*ad)->gauche));}else{

*ag = racine;coupure_ABR(racine->droit, valeur, &((*ag)->droit), ad);

}}

void insert_racine_ABR(ABR *racine, int valeur){ABR ag, ad, tmp;

if (*racine == NULL){

cree_racine(racine, valeur);return;

}cree_racine(&tmp, valeur);

coupure_ABR(*racine, valeur, &ag, &ad);tmp->gauche = ag;tmp->droit = ad;*racine = tmp;

}




. , ,

Complexite des operations : O(h) pour la plu-

part, dependente donc de la structure de l’arbre

de recherche.

Dans le pire des cas h = N .

Exemple :

21

13

10

7

12

En moyenne (ABR aleatoirement generes)

h = O(log N )

(voir [3], page 29).




. , ,

Remarque 1 : Si cles multiples, impossible (avec

les methodes explicitees) de trouver la premiereou la derniere apparition d’une cle.

Remarque 2 : Une idee pour palier une profon-

deur du ABR trop grande est d’assurer ”une

bonne densite des nœuds” ou d’assurer un equilibrag

entre le nombre des nœuds d’un sous-ABR gauche

par rapport au sous-ABR droit.




. , ,

Operations de rotations d’un ABR

But : Diminuer la profondeur des ABR ou les

faire satisfaire certaines proprietes.Rotations simples : gauche, droite.

xD

yDyG

y

x y

yG

x

xD

yD

rotation droite

rotation gauche

void rotation_gauche(ABR *x){

ABR y;

if ((*x==NULL) || ((y=(*x)->droit) == NULL))return;

(*x)->droit = y->gauche;y->gauche = *x;*x = y;

}

void rotation_droite(ABR *x){

ABR y;if ((*x == NULL) || ((y = (*x)->gauche) == NULL))

return;(*x)->gauche = y->droit;y->droit = *x;*x = y;

}




. , ,

Rotations doubles :

z

y

yG

zG

x

xD

zD

y

x

yG

xD

z

zG

zD

x

xD

z

zD

y

yG

yD

r o t a t i o n

d r o i t e

rotation gauche-droite

r o t a t i o n g a u c h e

void rotation_GD(ABR *x){

ABR y, z;if ((*x == NULL) || ((y = (*x)->gauche) == NULL) ||

((z = y->droit) == NULL))

return;(*x)->gauche = z->droit;y->droit = z->gauche;z->gauche = y;z->droit = *x;*x = z;

}




. , ,

Arbres rouge et noir

Definition : Un arbre rouge et noir (ARN) est

un ABR qui verifie les conditions suivantes :

1. Chaque nœud est soit rouge, soit noir.

2. Chaque descendant qui n’existe pas est rem-

placee par une feuille noire sans cle.

3. Si un nœud est rouge, ses fils sont noirs.

4. Chaque chemin qui relie un nœud a une feuilledescendente contient le meme nombre des

nœuds noirs.

Nœud interne = Nœud qui n’est pas feuille et

qui donc contient une cle.

La hauteur noire d’un nœud (notee hn(x)) estle nombre des nœuds noirs entre le nœud x est

une feuille.

Remarque 1 : Si r est la racine de l’ARN, alors :hn(r) ≤ h ≤ 2hn(r)

Ramarque 2 : Tout sous-arbre enracine en x a

au moins 2hn(x) − 1 nœuds internes.




. , ,

Propriete : La hauteur (profondeur) d’un ARN

ayant N nœuds internes est au plus egale a

2log2 (N + 1).

Preuve : D’apres la remarque 2 appliquee a la

racine r : N ≥ 2hn(r)−1, donc hn(r) ≤ log2 N + 1.

On applique apres la deuxieme partie de l’innegalite

de la remarque 1.

Exemple d’ARN :

30

25

23

22

28

38

35 40

429 12

1 10

18

15 20

7

13

21




. , ,

Operations sur un ARN et leurs complexite

– recherche, selection / suppression du min/max

calcul du predecesseur/successeur en O(log N )

car les procedures sont similaires que pour

les ABR et h est en O(log N ).

– insertion d’une feuille, suppression en O(log N )

aussi.

Les deux dernieres operations doivent, en plus,

garder les proprietes d’ARN a l’arbre.




. , ,

Insertion d’une feuille dans un ARN

Principe : On insere la feuille comme dans un

ABR classique, en gardant le chemin parcourudepuis la racine, et en associant la couleur rouge

a ce nouveau nœud. Tant que les proprietes d’un

ARN sont violees, on applique des recoloriages

et, peut-etre, une rotation en remontant vers la

racine. La racine sera noire.

Parmi les proprietes d’un ARN, seule qui peut

ne pas etre realisee est la 3, a savoir obtenir un

nœud et son pere de couleur rouge.




. , ,

r) cr eation nœud x ;couleur(x) = rouge ;tant que (x != racine) et (couleur(pere(x) == rouge) faire

si pere(x) == gauche(pere(pere(x)) alors

y = droite(pere(pere(x)) ;si couleur(y) = rouge alors

couleur(pere(x)) = noir ;couleur(y) = noir ;couleur(pere(pere(x))) = rouge ;x = pere(pere(x)) ;

sinon

si x = droit(pere(x)) alors

rotation-gauche(pere(x))fin si

couleur(pere(x)) = noir ;couleur(pere(pere(x)) = rouge ;rotation-droite(pere(pere(x)) ;

sinon

traitement symetrique

fin si

fin tant

couleur(racine) = noir ;




. , ,

Suppression d’un nœud dans un ARN

Principe : On supprime le nœud comme dans

un ABR clasique, en gardant le chemin depuis

la racine. Si le nœud supprime est noir, on doit

proceder de facon iterative a des recoloriages et

rotations. La racine sera noire.

La propriete des ARN qui est violee est cellesur la hauteur noire, on doit donc essayer de faire

de rotations et des coloriages afin de respecter

cette propriete.

(on effectuera au plus trois rotations).

voir [2], pages 273 – 286




. , ,

Arbres H-equilibres (AVL)

proposes dans annees ’60 par Adelson-Velskii et

Landis (AVL).

Definition : Soit T un ABR, pour tout nœud x

on peut calculer :

desequilibre(x) = hauteur(SG(x))−hauteur(SD(x))

ou SG(x) et SD(x) sont les sous-arbres gauche,

repectivement, droit de x.

Un nœud x est dit equilibre si

desequilibre(

x) = 0

La fonction desequilibre peut prendre autant des

valeurs negatives que positives.

Definition : Un ABR est dit arbre H-equilibre

(ou AVL), si pour tout nœud la fonction desequilibre

prend uniquement les valeurs -1, 0 et 1.




. , ,

Exemples d’AVL :

-1

0

0

11

-1

00

0

-1

1

-1




. , ,

Propriete : Pour tout arbre H-equilibre avec N nœuds la hauteur h verifie la relation :

log2 (N + 1) ≤ h + 1 < 1.44 log2 (N + 2)

Preuve :

1. Soit N max(h) le nombre maximum de nœuds d’un AVL

de profondeur h. Evidemment N ≤ N max(h). Alors :N max(h) = N max(h− 1) + N max(h− 1 ) + 1

et N max(0) = 1 et N max(1) = 3.(N max(h) correspond au nombre des nœud d’un arbrebinaire complet)Notons αh = N max(h) + 1. Alors

αh = 2αh−1

et α0 = 2. On deduit αh = 2h+1. Donc N max(h) =2h+1 − 1 et

h + 1 ≥ log2 (N + 1)

2. Soit N min(h) le nombre minimum de nœuds d’un AVLde profondeur h. Evidemment N ≥ N min(h). La condi-tion de minimalite se traduit par la relation recursive :

N min(h) = N min(h− 1) + N min(h− 2)

Par ailleurs N min(0) = 1 et N min(1) = 2.




. , ,

Notons β h = N min(h) + 1. Alors

β h = β h−1 + β h−2

avec β 0 = 2 et β 1 = 3L’equation associee est :

x2 = x + 1

avec les solutions φ = 1 +√ 52

et φ = 1−√ 52

.

Alors β h = aφh + bφh. En determinant a et b, on obtient :

β h = 1√

5(φh+3 − φh+3)

Donc N min + 1 = 1√

5(φh+3 − φh+3)

N + 1 ≥ 1√ 5

(φh+3− φh+3), d’ou N + 1 ≥ 1√ 5

(φh+3−1). Par

transformations successives :

h + 3 < 2 + 1

log2 φlog2 (N + 2)

Avec l’approximation 1

log2 φ ∼ 1.44 on obtient :

h + 1 < 1.44 log2 (N + 2)




. , ,

Complexite des operations

– recherche, min / max, predecesseur / suc-cesseur – O(log N )

– insertion – O(log N )

– suppression – O(log N )

Pour l’insertion et la suppression le principe est

le meme que pour les ARN : on trouve ”classi-

quement” l’endroit d’insertion/suppression, puis

on procede a des rotations successives afin de

garder la propriete d’AVL.




. , ,

Rotations sur AVLs

modifient les desequilibres des nœuds racine.

void rotation_gauche_AVL(AVL *x){

AVL y;

if ((*x==NULL) || ((y=(*x)->droit) == NULL))return;

(*x)->droit = y->gauche;y->gauche = *x;

((*x)->info)++;if (y->info < 0) (*x)->info -= y->info;y->info++;if ((*x)->info > 0) y->info += (*x)->info;

*x = y;}

void rotation_droite_AVL(AVL *x){

AVL y;

if ((*x == NULL) || ((y = (*x)->gauche) == NULL))return;

(*x)->gauche = y->droit;y->droit = *x;

((*x)->info)--;if (y->info > 0) (*x)->info -= y->info;y->info--;if ((*x)->info < 0) y->info += (*x)->info;*x = y;

}




. , ,

Insertion dans un AVL

int insert_AVL(AVL *racine, int valeur){

int ajouth, hplus;ajouth = 0;if (*racine == NULL){

*racine = (AVL)malloc(sizeof(struct noeud));

(*racine)->cle = valeur;(*racine)->info = 0;(*racine)->gauche = NULL;(*racine)->droit = NULL;return 1;

}if ((*racine)->cle > valeur){

hplus = insert_AVL(&((*racine)->gauche), valeur);

if (hplus != 0){(*racine)->info++;if (((*racine)->info == 1) || ((*racine)->info == 0))

ajouth = (*racine)->info;else{

if (((*racine)->gauche)->info == -1)rotation_gauche_AVL(&((*racine)->gauche));

rotation_droite_AVL(racine);

}}

}




. , ,

else{

hplus = insert_AVL(&((*racine)->droit), valeur);if (hplus != 0){

((*racine)->info)--;if (((*racine)->info == -1) || ((*racine)->info == 0))

ajouth = -(*racine)->info;else{

if (((*racine)->droit)->info == 1)

rotation_droite_AVL(&((*racine)->droit));rotation_gauche_AVL(racine);}

}}return ajouth;

}




. , ,

Suppression dans un AVLint supprime_AVL(AVL *racine, int valeur){

int hmoins, perdh;AVL tmp;perdh = 0;if (*racine == NULL) return 0;if (valeur < (*racine)->cle){

hmoins = supprime_AVL(&((*racine)->gauche), valeur);if (hmoins != 0){

((*racine)->info)--;if ((*racine)->info != -2)

perdh = 1 + (*racine)->info;

else{

if (((*racine)->droit)->info == 1)rotation_droite_AVL(&((*racine)->droit));

rotation_gauche_AVL(racine);if ((*racine)->info == 0)

perdh = 1;}

}}

elseif (valeur > (*racine)->cle){

hmoins = supprime_AVL(&((*racine)->droit), valeur);if (hmoins != 0){

((*racine)->info)++;if ((*racine)->info != 2)

perdh = 1- (*racine)->info;else

{if (((*racine)->gauche)->info = -1)

rotation_gauche_AVL(&((*racine)->gauche);rotation_droite_AVL(racine);if ((*racine)->info == 0)

perdh = 1;}

}}




. , ,

else{

if ((*racine)->gauche == NULL){

tmp = *racine;*racine = tmp->droit;free(tmp);return 1;

}if ((*racine)->droit == NULL){

tmp = *racine;*racine = tmp->gauche;

free(tmp);return 1;}else{

tmp = (*racine)->gauche;while (tmp->droit != NULL) tmp = tmp->droit;(*racine)->cle = tmp->cle;tmp->cle = valeur;hmoins = supprime_AVL(&((*racine)->gauche), valeur);

if (hmoins != 0){

((*racine)->info)--;if ((*racine)->info != -2)

perdh = 1 + (*racine)->info;else{

if (((*racine)->droit)->info == 1)rotation_droite_AVL(&((*racine)->droit));

rotation_gauche_AVL(racine);if ((*racine)->info == 0)

perdh = 1;}

}}

}return perdh;

}




. , ,

Structure Recherche Insertion suppression

Vect. n-ord. O(N ) O(1) O(N )Liste n-ord. O(N ) O(1) O(1)

Vect. ord. O(log N ) O(N ) O(N )Liste ord. O(N ) O(1) O(1)

ABR O(h) O(h) O(h)ARN O(log N ) O(log N ) O(log N )AVL O(log N ) O(log N ) O(log N )




. , ,

B-arbres

Structures de donnees adpatees a la recherche

externe.

Definition : Un B-arbre d’ordre m est un arbre

de recherche tel que :

– chaque nœud contient au plus 2m elements(cles) et a donc au plus 2m + 1 fils

– chaque nœud, sauf la racine, contient au

moins m elements et donc au moins m + 1

fils ; la racine contient au moins 1 element

et donc au moins 2 fils.

– Toutes les feuilles sont situees a la meme

distance par rapport a la racine.

Exemple :

6 13 17

20

30 45

22 25 28 32 36 38 40 50 53 55 571 5 7 9 10 11 14 16 18 19




. , ,

Propriete : La hauteur d’un B-arbre d’ordre m

ayant N nœuds est majoree par logm+1 (N +12 ).

La hauteur du B-arbre dicte le nombre d’acces

a la memoire secondaire.

En pratique m compris entre 40 et 250 (1000).

Exemple : Si m = 250, dans un B-arbre sur 2

niveaux on peut garder plus de 108 elements.

La recherche dans un B-arbre se fait depuis le

nœud racine en descendant vers les feuilles ; au

niveau d’un nœud on applique la recherche di-chotomique.

L’insertion et la suppression deviennent labo-

rieuses si le B-arbre doit changer de hauteur.

(Voir [1], page 173–206.)

Remarque : Si m petit (m = 2), le B-arbrepeut etre utilise comme structure de donnees

de recherche dans la memoire principale. Ses

performances sont tres bonnes (operations en

O(log N )).




. , ,

Tables de hachage

Structures de donnees adpatees a la recherche

externe

Espace de stockage

+

Function de hachage

La place d’un element dans la table est calculee

avec la fonction de hachage.

Soit h : U → {1, 2, . . . m} ou U tres grand par

rapport a E.h(x) = i

signifie l’element x est memorise dans la position

i. h(x) appele valeur de hachage primaire.

Conditions sur h :

– h simple a calculer– h doit etre uniforme :

∀x ∈ U, ∀i ∈ {1, 2, . . . m}, P ([h(x) = i]) = 1/m

– Idealement h injective pour E .




. , ,

Si h injective, la recherche d’un element x est la

suivante :

– calcul de h(x), valeur i

– recherche dans la case i du tableau. Si case

vide, recherche echouee. Soit e l’element

situe en i.

– Si x = e, succes– Si x = e, recherche echouee

Si on veut ajouter x, dans le deuxieme cas, (h

n’est plus injective !), on doit resoudre une

collision primaire.

En realite, h n’est pas injective sur E , si m n’est

pas trop grand par rapport a N , meme si h est

uniforme.

Deux classes de methodes de hachage :

– Methodes de resolution des collisions par

chaınage

– Methodes de resolution des collisions par

calcul




. , ,

Selection

”Trouver l’element min / max d’un ensemble.”

Selection du min dans un vecteur T de taille N :

min ← T [1]for i = 2 to N do

if T [i] < min thenmin

← T [i]

endif endfor

Complexite : N − 1 comparaisons (optimal).

Pareil pour le max.

Si on cherche le min et le max du meme tableau.

min ← T [1] ; max ← T [1]for i = 2 to N do

if T [i] < min thenmin ← T [i]

else if T [i] > max thenmax ← T [i]

endif endif

endfor

cM.Mathieu Selection



. , ,

Complexite : Entre N − 1 et 2(N − 1) comparai-

sons.

On peut montrer (par induction) que le nombre

minimum de comparaisons pour trouver le min

et le max est 3N

2 −2.




. , ,

Solution optimale :

if T [1] < T [2] then

min ← T [1] ; max ← T [2]else

min ← T [2] ; max ← T [1]endif for i = 3 to N step 2 do

if T [i] < T [i + 1] thenif T [i] < min then

min

←T [i]

endif if T [i + 1] > max then

max ← T [i + 1]endif

elseif T [i + 1] < min then

min ← T [i + 1]endif

if T [i] > max thenmax ← T [i]

endif endif

endforif N impaire then

if T [N ] < min thenmin ← T [N ]

elseif T [N ] > max then

max ← T [N ]endif

endif endif




. , ,

File de priorites

Structure de donnees qui permet les operations

suivantes :

1. Inserer un element

2. Selectionner l’extremum

3. Supprimer l’extremum

4. Supprimer n’importe quel element de l’en-semble

(Extremum signifie min ou max.)




. , ,

Tas

(Appele aussi arbre maximier/minimier ou heap)Definition : Un tas est une arborescence :

– binaire et chaque nœud contient un cle

– complete

– verifiant la suivante :

Propriete de structure : Pour tout nœud du

tas sa cle est plus petite ou egale que les cles

situees dans ses sous-arborescences gauche et

droite.

Exemple :

1

5 3

6 8

9

7

11 10

9

15 13




. , ,

Remarque 1 : La hauteur h d’un tas est loga-

rithmique :

log2

(N + 1)−

1 ≤

h < log2

(N + 1)

Remarque 2 : La racine du tas est l’element min.

Remarque 3 : Toute sous-arborescence d’un tas

est un tas.

Propriete de representation : Un tas de N elemen

peut se representer par dans un tableau de meme

taille, tout nœud est represente sur l’indice i dutableau, i etant le rang du nœud lors du parcours

par niveaux.

1

2 3

4 4 6 7

8 9 10 11 12

1

5 3

6 8

9

7

11 10

9

15 13

1 2 8 9 123 4 5 6 7 10 11

1 7 9 6 8 11 10 155 3 13 9




. , ,

Remarque : Si T [i] est un element dans le ta-

bleau de representation d’un tas, alors T [i/2] est

son pere et T [2i], T [2i + 1] ses fils.

Suppression du minimum d’un tas

1. Supression de la racine

2. Remplacement par le dernier element du tas3. Reconstruction du tas par un parcours de-

puis la racine vers les feuilles, en procedant

par des echanges.

Suppression d’un element d’un tas

1. Remplacement de l’element par le dernierelement du tas

2. Reconstruction du tas par un parcours de-

puis cet element soit vers la racine, soit vers

les feuilles, en procedant par des echanges.




. , ,

Insertion dans un tas

1. Ajout du nouvel element sur la derniere po-

sition.

2. Reconstruction du tas par un parcours de-

puis cet element vers la racine, en procedanta des echanges.

Complexite : O(log N ) pour l’insertion et les sup-

pressions, car pendant le parcours on avance ou

on descend dans le tas et a chaque niveau on

fait un nombre constant d’operation (au total auplus log N echanges et 2 log N comparaisons).




. , ,

void supprime_min_tas(int T[], int *N){

int j, fils;T[1] = T[*N];(*N)--;

j = 1 ;while(j < (*N)/2){

fils = j*2;if ((fils+1 <= (*N)) && (T[fils+1] < T[fils]))

fils = fils+1;if (T[j] < T[fils])

break;else{

echange(T, j, fils);j = fils;

}}return;

}

void insert_tas(int T[], int *N, int valeur){

int j, pere;

(*N)++;T[*N] = valeur;j= *N;pere = j/2;while ((pere >= 1) && (T[j] < T[pere])){

echange(T,j, pere);j = pere;pere = j/2;

}

}

void echange(int T[], int i, int j){

int tmp;tmp = T[i];T[i]= T[j];T[j] = tmp;

}




. , ,

Tri

Criteres d’analyse :

– representation des donnees

– type de tri : in situ ou avec memoire supplemen

– stabilite (garde l’ordre initiale des elements

egaux)

Complexite : moyenne et dans le pire des cas.

Apprecier la complexite :

– nombre comparaisons

– nombre d’echanges

cM.Mathieu Tri



. , ,

Complexite. Borne inferieure

Question : quelle est la meilleure complexite d’unalgorithme de tri ?

Arbres de comparaisons pour trier

N = 2 :

><

x1 : x2

x2, x1x1, x2

N = 3 :

x1, x2, x3

x1 : x2

><

x2 : x3

<

x1 : x3

< >

x2, x3, x1

x2 : x3

x3, x2, x1

< >

x1 : x3

x3, x1, x2

< >

x2, x1, x3

x1, x3, x2

>

cM.Mathieu Tri



. , ,

Remarque 1 : La complexite est donnee par la

hauteur de l’arbre de comparaisons associe.

Remarque 2 : Tout arbre de comparaisons a au

moins N ! feuilles, chaque feuille correspond a

une permutation de l’ensemble {1, 2, . . . N }.

Propriete : La hauteur minimale d’un arbre de

comparaisons pour un ensemble de taille N est

log2 (N !).

Theoreme : Tout algorithme de tri demande,

dans le cas le plus defavorable, au moins O(N log N )

comparaisons.

Preuve : Il suffit de montrer que log2 (N !) =

O(N log N ).On travaille sur la formule de Stirling :

N ! ≈√

2πN

N

e

N

cM.Mathieu Tri



. , ,

Complexite des algorithmes de tri :

– quadratique – O(N 2)

– sub-quadratique – O(N log N ) en moyenne,

O(N 2) dans le pire des cas

– optimale – O(N log N )

– lineaire – O(N ) (pour des ensembles parti-

culiers a trier)

cM.Mathieu Tri



. , ,

Tri bulles

Principe : Par echanges successifs entre elements

voisins on fait remonter l’element le plus petit a

la premiere place.

for k = 1 to N − 1 do

for j = N to k + 1 step -1 do

if T [ j − 1] > T [ j] then

echange(T, j − 1, j)

endif

endforendfor

Caracteristiques : Simple a mettre en œuvre,

stable, travaille sur tableau, quadratique

Remarque : Si lors d’un etape il n’y a pas d’echange

alors le tableau est trie, on peut s’areter.

cM.Mathieu Tri



. , ,

Analyse :– nombre de comparaisons

C N =

N −1

k=1

(N + 1− k − 1) =

N −1

k=1

(N − k) = N (N − 1)

2


– dans le cas le plus favorable (tableau deja

trie)

E N = 0

– dans le pire des cas (tableau en ordre

inverse)

E N = C N = N (N − 1)

2– en moyenne

E N = N (N

−1)

4

cM.Mathieu Tri



. , ,

Preuve :

Soit T un tableau a trier et T s le tableau inverse :

T s[i] = T [N + 1 − i]

Si on execute le tri bulles sur T et T s simul-

tanement, a chaque comparaison on execute un

seul echange soit dans T , soit dans T s.

Notons σS le nombre d’echanges necessaires pour

un tableau S quelconque.

Alors : σT + σT s = N (N − 1)

2

.

Le nombre moyen d’echanges est :

E N =

Ttableau

p(T )σT =

= 1

2

T tableau( p(T )σT + p(T s)σT s) =

= 1

2

N (N − 1)

2 =

N (N − 1)

4

cM.Mathieu Tri



. , ,

Tri par selection

Principe : A chaque etape i, i = 1, N − 1, on

cherche le min parmi les elements

T [i], T [i + 1], . . . T [N ]

et on le place sur la position i.

Ainsi a la fin de l’etape i les elements

T [1], T [2], . . . T [i]

sont definitivement tries.

Caracteristiques : stable, simple a mettre en œuvre,

quadratique

for i = 1 to N −

1

min = i ; valmin = T [i] ;

for j = i + 1 to N

if T [ j] > valmin then

min = j ;

valmin = T [ j] ;

endif

endfor

if i = min

echange(T,i,min)

endif

endfor

cM.Mathieu Tri



. , ,

Complexite :

– nombre de comparaisons

C N =N −1i=1

(N − i) = N (N − 1)

2


– le cas le plus favorable (elements tries)

E N = 0

– le pire des cas (elements tries a l’envers)

E N = N − 1

– moyen O(N ) (voir [4])

cM.Mathieu Tri



. , ,

Tri par insertion

Principe : A chaque etape i (i = 2, N ), on sup-

pose que le tableau

T [1], T [2],...,T [i − 1]

est trie (provisoirement) et on insere l’element

T[i].

Remarque : Le calcul de la position a inserer

peut se faire soit par une recherche sequentielle,

soit par une recherche dichotomique.

Schema :

for i = 2 to N

inserer T [i] a son rang parmi T [1], . . . T [i − 1]

endfor

Caracteristiques : travaille sur tableau (on peut

adapter si insertion sequentielle pour liste), stable

(a assurer)

cM.Mathieu Tri



. , ,

Tri par insertion sequentielle

for i = 2 to N

aux = T [i] ;

j = i − 1 ;

while j ≥ 1 and T [ j] > aux do

T [ j + 1] = T [ j] ; j = j − 1 ;

endwhile

if j + 1 = i

T [ j + 1] = aux ;

endif

endfor

Ameliorations possibles

– mettre l’element minimum a la position premie

du tableau, ainsi plus besoin d’un test sur

j dans la bouche while– avant le faire la recherche de la position de

la variable aux la comparer avec le premier

element et tout decaler d’une position si

aux < T [1]

cM.Mathieu Tri



. , ,

Complexite :


– le cas le plus favorable (tableau trie)

C N = N − 1

(un seul test pour se rendre compte que

T [i] se trouve sur la bonne place)

– le pire des cas (tableau trie a l’envers)

C N =N

i=2

i = N (N + 1)

2 − 1

(i comparaisons a chaque etape i)

– moyen

C N =N

i=2

i

2 =

N (N + 1)

4 − 1

2

(en moyenne on fait i/2 tests a chaque

etape i en supposant que le tableau est

aleatoirement genere)

– nombre de tranferts (pas d’echanges)

T N = C N − (N − 1) = C N − N + 1

(on fait toujours un test de plus que les

comparaisons a chaque etape).cM.Mathieu Tri



. , ,

Tri par insertion dichotomique

for i = 2 to N

if T [i] < T [i − 1] then pos = rangdich(T, 1, i − 1, T [i]) ;aux = T [i] ;for j = i − 1 to pos step -1

T [ j + 1] = T [ j] ;endforT [ pos] = aux ;

endif endfor

La fonction rangdich calcule par une recherchedichotomique le plus petit element qui soit plusgrand que la valeur a analyser :

fonction rangdich(T [], g, d, valeur)if g >= d then

return gendif m = (g + d)/2 ;

if valeur < T [m] thenreturn rangdich(T,g,m,valeur)else

return rangdich(T, m + 1, d, valeur)endif

endfonction

cM.Mathieu Tri



. , ,

Complexite :


– le meilleur cas (tableau trie)

C N = N − 1

– le pire des cas (tableau trie a l’envers)

C N = O(N log N )

– nombre de transferts

– le meilleur cas

T N = 0

– le pire des cas

T N = O(N 2)

cM.Mathieu Tri



. , ,

Avantages (des 2 methodes de tri par insertion) :

– tri par insertion dichotomique optimal enterme de comparaisons

– stables

– tri par insertion sequentielle adaptable pour

liste chaınees

Desavantages :

– nombre important de transferts dans le pire

des cas et en moyenne

– les transferts se font uniquement entre voi-

sins

cM.Mathieu Tri



. , ,

Tri par insertion sur liste chaınee

Variante 1 :

void tri_insertion_liste_var1(liste *maliste){

liste l2, l3;liste pt;

if (*maliste == NULL) return;

l2 = *maliste;l3 = (*maliste)->next;l2->next = NULL;

while (l3 != NULL){

pt = l3;l3 = l3->next;insert_liste_element(&l2, pt, NULL);

}

*maliste = l2;}

Complexite :

– moyenne O(N 2)

– liste triee O(N 2)

– liste triee a l’envers O(N )

cM.Mathieu Tri



. , ,

Variante 2 :

void tri_insertion_liste_var2(liste *maliste){liste l2, l3;liste dernier, pt;

if (*maliste == NULL) return;

l2 = *maliste;

l3 = (*maliste)->next;dernier = *maliste;

while (l3 != NULL){

if (l3->cle >= dernier->cle){

dernier = l3;l3 = l3->next;

}else{

/* il faut faire une insertion */pt = l3;l3 = l3->next;pt->next = NULL;dernier->next = l3;insert_liste_element(&l2, pt, dernier->next);

}}*maliste = l2;

}

cM.Mathieu Tri



. , ,

Complexite :

– moyenne O(N 2)

– liste triee a l’endroit ou a l’envers O(N )La fonction d’insertion commune :

void insert_liste_element(liste *tete, liste pt, liste fin{

liste temp, prev;int valeur;

valeur = pt->cle;if (valeur <= (*tete)->cle){

pt->next = *tete;*tete = pt;return;

}else{

prev = *tete;temp = (*tete)->next;while ((temp != fin) && (valeur > temp->cle)){

prev = temp;temp = temp->next;

}prev->next = pt;pt->next = temp;

}return;

}

cM.Mathieu Tri



. , ,

Tri Shell

Principe : C’est un tri par insertion qui realise le

tri, non plus sur l’ensemble, mais sur des sous-

ensembles d’elements eloignees a la distance h.

On fait varier h dans l’ensemble :

N ≥ ht > ht−1 > . . . h2 > h1 = 1

En pratique h est choisi dans la suite :

1, 4, 13, 40, . . . , ht = 3ht−1 + 1

Caracteristiques : Sub-quadratique, efficace pour

N raisonablement grand (N < 5000), simple aprogrammer, instable

cM.Mathieu Tri



. , ,

void tri_shell(int T[], int N){

int h, i, j, aux;

for (h = 1; h <= N / 9; h = 3*h +1);for (; h > 0; h = h/3)

for (i = h+1; i < N; i++){

aux = T[i]; j = i;while ((j >= h) && (T[j-h] > aux)){

T[j] = T[j-h];j -= h;

}T[j] = aux;

}

}

Complexite : Deux conjectures O(N 54) et

O(N log2 N ).

Borne superieure : N 32 pour le nombre de com-

paraisons pour la suite de h :1, 4, 13, 40, . . .

cM.Mathieu Tri



. , ,

Tri rapide (quicksort)

Decouvert par C.A. Hoare en 1962

Principe :

– partager l’ensemble de depart en 2 sous-

ensembles tels que tous les elements du

premier soient strictement plus petits que

les elements du second sous-ensemble

– trier ainsi recursivement les 2 sous-ensembles.

fonction trirapide(T [], g , d)

if g < d then

partage(T , g , d , j) ;

trirapide(T , g , j − 1) ;trirapide(T, j + 1, d) ;

endif

endfonction

L’appel initial est trirapide(T, 1, N ).

Le partage de l’ensemble T se fait par rapport

a la valeur T [g], appellee pivot et qui se trou-

vera a sa place definitive j apres l’execution de

partage(T , g , d , j).cM.Mathieu Tri



. , ,

fonction partage(T [], g , d , j)

l = g + 1 ;

j = d ;

while l ≤ j do

while T [ j] > T [g] do

j = j − 1 ;

endwhile

while l ≤ j et T [l] ≤ T [g] dol = l + 1 ;

endwhile

if l < j then

echange(T , l , j) ;

l = l + 1 ;

j = j − 1 ;

endif

endwhile

echange(T , g , j) ;

endfonction

Complexite de la fonction : Si N est la taille du

tableau T , alors on effectue N − 1 (ou N + 1)

comparaisons et au plus N 2 echanges.

cM.Mathieu Tri



. , ,

Analyse de l’algorithme

(en nombre de comparaisons)

Soit p la position du pivot, alors le nombre de

comparaisons est :

C N = C p−1 + C N − p + N − 1

– Dans le meilleur cas – le pivot est la valeur

mediane :

C N = 2C N 2

+ N − 1

Donc C N

= O

(N

logN

)

– Dans le pire des cas – pivot est le plus petit

element :

C N = C N −1 + C 1 + N − 1

Donc C N = O(N 2)

– En moyenne.On peut prouver par induction que

C N < 2N log N

cM.Mathieu Tri



. , ,

Si l’ensemble a trier est aleatoirement genere, laprobabilite que le pivot soit sur la position p esttoujours 1

N . Alors :

C N = N − 1 + 1

N

N p=1

(C p−1 + C N − p)

Evidemment C 0 = 0 et C 1 = 0.

C N peut s’ecrire aussi :

C N = N − 1 + 2N

N

−1

i=1C i

on en deduit :

NC N = (N + 1)C N −1 + 2N

C N

N + 1 =

C N

−1

N +

2

N + 1 =

= C N −2

N − 1 +

2

N +

2

N + 1 =

= . . . = C 2

3

+N

k=3

2

k + 1

La valeur C N

N + 1 peut s’approximer par :

2 N

1

1

xdx = 2 loge N

cM.Mathieu Tri



. , ,

Variantes. Optimisations

1. Choisir le pivot au hasard.

2. Partager l’ensemble a trier en 3 : un sous-

ensemble strictement inferieur au pivot, un

sous-ensemble dont tous les elements sont

egaux au pivot et un autre sous-ensemble

strictement superieur au pivot. Cette version

sera stable.

3. Derecursiver un niveau de la fonction, l’appel

recursif etant fait pour le plus petit sous-ensemble. Gain de temps.

4. Du fait que pour N autour de 10 (entre 5

et 15), les performances du tri rapide sont

inferieures aux celles du tri par selection (ou

par insertion), appliquer dans la procedure

recursive le tri rapide uniquement si la taille

des sous-ensembles est suffisemment grande.

cM.Mathieu Tri



. , ,

Caracteristiques du tri rapide :

non-stable, sub-optimal, adapte aux tableaux,

recursif.

Le tri rapide se trouve implante au niveau de lalibrairie stdlib. Son prototype est le suivant :

void qsort(void *base, size_t nel, size_t width,int (*compar) (const void *, const void *));

ou base est le vecteur a trier, nel le nombre de

ses elements et width la taille d’un element. La

fonction compar indique la procedure de compa-

raisons entre deux elements du tableau.

cM.Mathieu Tri



. , ,

Tri par tas (heapsort)

Principe :

– organiser l’ensemble a trier en tas (maxi-

mier ou minimier)

– iterativement, extraire l’extremum (le max

ou le min) et le placer en fin de tas

– a la fin de la procedure les elements seronttries en ordre (croissant ou decroissant)

L’organisation du tableau en tas peut se faire,

par exemple, par des insertions successives.

void tri_tas(int T[], int N){

int i, j, aux;j = 1 ;for (i = 2; i <= N; i++)

insert_tas(T, &j, T[i]);for (i = 1; i <= N; i++){

echange(T, 1, j--);equilibre_bas_tas(T, j, 1);

}}

Attention ! Le tableau est indexe depuis 1.

cM.Mathieu Tri



. , ,

Complexite– Constrution du tas

N − 1 appels de insert tas. La complexite

de la fonction est fonction de la hauteur du

moment du tas.

N −1i=1

log2 i = Θ(N log N )

– Suppressions successives

N appels de equilibre tas bas dont la com-

plexite est log2 (N + 1 − i), i = 1, N .

N i=1

log2 (N + 1 − i) = Θ(N log N )

Complexite en moyenne et dans le pire des cas :

O(N log N ).

Caracteristiques : pas stable, optimal, adapte

aux tableaux.

cM.Mathieu Tri



. , ,

Autre construction du tas

Remarque : Si on considere le tableau initial

comme un tas (potentiel), les position compriseentre N

2 + 1 et N sont des feuilles, donc des

tas de taille 1.

Il suffit de parcourir les nœuds non-feuilles de-

puis le dernier jusqu’a la racine en equilibranttoujours le tas vers le bas. Ainsi on s’assure que

les sous-arbres sont des tas et apres avoir passe

dans la racine l’arbre entier sera un tas.

void tri_tas2(int T[], int N){

int i, j;for (i = N/2; i >= 1; i--)

equilibre_bas_tas(T, N, i);j = N ;for (i = 1; i <= N; i++){

echange(T, 1, j--);equilibre_bas_tas(T, j, 1);

}}

Complexite : au plus 2N comparaisons

La complexite du tri reste enchangee.cM.Mathieu Tri



. , ,

Tri par fusion

Fusion des deux ensembles

Si deux ensembles sont tries (dans le meme

sens), l’operation de fusion permet de construire

l’ensemble reunion des deux, lui aussi trie.

Fusion sur tableaux

void fusion(int T[], int S[], int U[], int N, int M){

int i, j, k;T[N] = MAXINT;

S[M] = MAXINT;for (i = 0, j = 0, k = 0; k < M+N; k++)

U[k] = (T[i] <= S[j]) ? T[i++] : S[j++];}

Les elements T [N ] et S [M ] sont appeles sentinelles.

Complexite : O(N + M ) operations (comparai-

sons et attributions). Espace memoire supplementa

pour le resultat : M + N .

cM.Mathieu Tri



. , ,

Fusion sur listes chaınees

liste fusion_liste1(liste l1, liste l2)

{liste res;struct element u;u.next = NULL;res = &u;while((l1 != NULL) && (l2 != NULL)){

if (l1->cle <= l2->cle)

{res->next = l1;l1 = l1->next;res = res->next;

}else{

res->next = l2;

l2 = l2->next;res = res->next;}

}if (l1 != NULL)

res->next = l1;if (l2 != NULL)

res->next = l2;

return u.next;}

Complexite : Au plus O(N + M ) operations. Pas

d’espace memoire supplementaire.

cM.Mathieu Tri



. , ,

Si les listes finissent avec un element senti-

nelle auto-referent Z qui contient la valeur NBMAX :

z

MAXINT

l’operation de fusion devient plus compacte a

ecrire (moins de tests) :

liste fusion_listeZ(liste l1, liste l2){

liste res;struct element u;u.next = Z;res = &u;do{

if (l1->cle <= l2->cle){

res->next = l1;l1 = l1->next;res = res->next;

}else{

res->next = l2;l2 = l2->next;res = res->next;

}}while (res != Z);return u.next;

}

cM.Mathieu Tri



. , ,

Tri par fusion

Principe :

– si l’ensemble est de petite taille, il est trie

”normalement”

– sinon, partager l’ensemble en deux

sous-ensembles de meme taille

– appliquer recursivement le tri par fusion sur

les deux sous-ensembles– effectuer le fussion des deux sous-ensembles

tries

Caracteristiques : stable (car la fusion est stable),

optimal, mieux adapte aux listes chaınees.

cM.Mathieu Tri



. , ,

Tri par fussion sur tableaux

Tres difficile de realiser un tri par fusion sur

place pour un tableau.

Solution utilisant un espace memoire supplementair

egale a la taille de l’ensemble a trier (tableau S).

void tri_fusion(int T[], int g, int d){

int i, j, m, k;if (g == d) return;

m = (g + d) / 2;tri_fusion(T, g, m);tri_fusion(T, m+1, d);for (i = m; i >= g; i--)

S[i] = T[i];for (j= m+1; j <= d; j++)

S[(d + m + 1) - j] = T[j];for (k = g, i = g, j = d; k <= d; k++)

T[k] = (S[i] <= S[j]) ? S[i++] : S[j--];}

cM.Mathieu Tri



. , ,

Tri par fusion pour listes

void tri_fusion_liste(liste *l){liste l1, l2, tmp;int i, N;

N = longueur_liste(*l);if (N <= 1) return;l1 = *l; l2 = *l;

tmp = NULL;for (i = 0; i < N/2; i++){ tmp = l2; l2 = l2->next; }

tmp->next = NULL;tri_fusion_liste(&l1);tri_fusion_liste(&l2);*l = fusion_liste(l1, l2);

}

void tri_fusion_listeZ(liste *u){

liste l1, l2, tmp;if ((*u)->next == Z) return;l1 = *u; tmp = *u; l2 = (*u)->next->next->next;while (l2 != Z)

{tmp = tmp->next; l2 = l2->next->next;}l2 = tmp->next;

tmp->next = Z;tri_fusion_listeZ(&l1);tri_fusion_listeZ(&l2);*u = fusion_listeZ(l1, l2);

}

cM.Mathieu Tri



. , ,

Dans le deux fonction on partage la liste initiale

en deux sous-listes contigues qui finissent par

NULL ou par la sentinelle Z.

Complexite :

Soit T (N ) le temps de la fonction de tri par

fusion (n’importe quelle variante). Ce temps se

decrit par la relation de recurrence suivante :

T (N ) = kN + T

N

2

+ T

N −

N

2

La solution de cette equation est en Θ(N log N ).

cM.Mathieu Tri



. , ,

Tableau comparatif des methodes de tri

Methode Compl. moy. Compl. pire Stable Structure

Bulles O(N 2) O(N 2) oui tableauSelection O(N 2) O(N 2) oui tableau

Insert. seq. O(N 2) O(N 2) oui tabl/listeShell O(N 1.25) O(N 1.5) non tableau

Rapide O(N logN ) O(N 2

) non tableauInsert. dich. O(N logN ) O(N logN ) oui tableau

Fusion O(N logN ) O(N logN ) oui listeTas O(N logN ) O(N logN ) non tableau

cM.Mathieu Tri



. , ,

Tris lineaires

Si les valeurs a trier sont particulieres, d’autres

methodes de tri peuvent s’appliquer. Leur com-

plexite est parfois lineaire.

– tri par denombrement

– tri par base

– tri par paquets

cM.Mathieu Tri



. , ,

Tri par denombrement

Hypothese : Les valeurs a trier sont des entiers

compris entre 1 et k, ou k est raisonnablement

petit (k = O(N )).

Principe :– dans un vecteur auxiliaire C on compte le

nombre d’apparitions de chaque element j

(compris entre 1 et k) dans le tableau T

– on calcule ensuite, toujours dans C , pour

chaque j (1 ≤

j ≤

k) le nombre d’elements

du tableau T plus petits que lui

– si j apparaıt une seule fois dans T , C [ j] in-

dique la position de j dans le vecteur trie ;

si j apparaıt plusieurs fois dans T , C [ j] in-

dique la derniere position dans le tableau

trie occupee par j– il suffit de parcourir les elemets du tableau

T depuis la fin du tableau pour leur fixer la

position finale dans le tableau trie.

cM.Mathieu Tri



. , ,

for j = 1 to k

C [ j] = 0

endfor

for i = 1 to N C [T [i]] = C [T [i] ] + 1

endfor

for j = 2 to k

C [ j] = C [ j] + C [ j − 1]

endfor

for i = N to 1 step -1V [C [T [i]]] = T [i]

C [T [i]] = C [T [i]] − 1

endfor

Le tableau trie est V . Le tableau C sert de ta-

bleau compteur de positions.

Attention ! Les tableaux sont indexes depuis la

position 1 !

Complexite :

Plusieurs boucle for de taille N et k. Donc com-

plexite en O(N + k) = O(N ), si k = O(N ).

Caracteristiques :

stable, lineaire, espace memoire supplementaire

cM.Mathieu Tri



. , ,

Tri par base

Algorithme utilise pour trier des cartes perforees.

Hypothese :

Les valeurs a trier sont representees sur c chiffres.

Les valeurs a trier sont xi = si1si2sic, i = 1, N ,

ou sij, j = 1, c chiffres.

Tri de x1, x2 . . . xN = tri lexicographique.

Principe :

Trier le tableau initial depuis le chiffre le moins

significatif jusqu’au chiffre le plus significatf.

for j = c to 1

tri stable selon le chiffre j

endfor

cM.Mathieu Tri



. , ,

Complexite :

Si on utilise a l’interieur de la boucle for le tri

par denombrement dont la complexite est en

O(N + k) ou k est la base de representation (ha-

bituellement k = 2 ou k = 10 ou k = 16), la

complexite totale est O(cN + ck) = O(N ).

Si on utilise un tri sans espace memoire supplementa

la complexite est O(N log N ).

cM.Mathieu Tri



. , ,

Tri par paquets

Hypothese :

Les valeurs a trier sont uniformement distribueesdans l’intervalle [0, 1[.

Principe :– tous les elements T [i] seront associes a des

listes disjoinctes L[ j], j = 0, N − 1 ; la liste

L[ j] contient les elements compris entre jN

et j + 1

N – on trie separemment les listes L[ j], j =

0, N − 1

– on concatene les listes L[ j] dans l’ordre j =

0, N − 1– la liste concatenee contient les elements

tries.

for i = 1 to N

ajout de T [i] a la liste L[

nT [i]

]

endfor

for j = 0 to N − 1

tri liste L[ j]

endfor

concatenation L[ j], j = 0, N − 1.

cM.Mathieu Tri



. , ,

Complexite :

Soit n j le nombre d’elements de la liste L[ j].

Le temps attendu pour trier L[ j] est :

E [O(n2 j )] = O(E [n2

j ])

Le temps total moyen pour trier toutes les listes

est :N −1 j=0

O(E [n2 j ]) = O(

N −1 j=0

E [n2 j ])

Si T [i], i = 1, N uniformement distribues, alors

k = n j suit la boi binomiale

B(k; N, p), p = 1

N .

Alors :

E[nj] = Np = 1

Documents

M´ethodes de programmation Algorithmes de recherche, tri et s´election