[PDF] Algorithmes de tris





Previous PDF Next PDF



I. Tri par sélection

On fusionne les deux tableaux triés en un tableau trié. 2 - code Python a) Fusion de deux listes triées L'algorithme de tri-fusion de mani`ere récursive s' ...



Algorithmes de tri interne (4) [tr] Méthodes par sélections

Le tri par sélection en itératif transcrit la version récursive. Procédure trSelection. (Tri par sélection en itératif). Action trSelection ( DR A : Element ( 



1 Tri par sélection

• la fonction récursive de tri qui si le tableau contient plus d'un éléments On le choisit donc au hasard ! Implémentons cette méthode de tri sous Python :.



Les algorithmes de tris et leurs implémentations en Python

Comme le tri par fusion le tri par segmentation est donc dichotomique. La Comme on le constate



CAPES MATHS OPTION INFORMATIQUE ALGORITHMIQUES DE TRI

Tri par fusion interne a. Ecrire en Python une version récursive de l'algorithme du tri par fusion d'un tableau de réels. def fusion(gauche droite):.



Algorithmes de tri interne (2) [tr] Méthodes par insertions

La procédure de tri par insertion de façon récursive ins`ere en décalant les éléments vers la gauche



Cours 8 – Tris I Algorithme naïf : tri par sélection

Implémentation en Python. def tri_selection(L): . 1. Page 2 On peut alors écrire une fonction récursive mettant en œuvre l'algorithme de tri par fusion.



Algorithmes classiques

1) Tri par sélection: Ce tri est parfois appelé naïf. Le principe consiste à Exercice 7 : Écrire un programme Python permettant de réaliser un tri à bulle ...



Informatique en CPGE (2018-2019) Algorithmes de tri 1 Introduction

Le tri par insertion d'un tableau à n éléments [t0



jean-manuel Mény– IREM DE LYON () Algorithmique 2013 1 / 39

18 мар. 2013 г. Procédure fusion Python. Exercice `a rendre 2. On propose ci-dessous une ... Version récursive du tri par fusion. Vous avez `a rendre (cf ...



1 Tri par sélection

1 Tri par sélection Implémentons cette méthode de tri sous Python : ... la fonction récursive de tri qui si le tableau contient plus d'un éléments le ...



Algorithmes de tri interne (4) [tr] Méthodes par sélections

Pour écrire de façon récursive le tri par sélection nous partons de la définition suivante. Étant donné un tableau de n éléments :.



1 Algorithmes de tri

Appliquer l'algorithme de tri par sélection à la mains pour trier les listes Celà ne pose pas de problème en Python car les paramètres sont passés par ...



Algorithmes de tri interne (2) [tr] Méthodes par insertions

La procédure de tri par insertion de façon récursive ins`ere en décalant les éléments vers la gauche



TP no 8 : Quelques algorithmes de tri

On peut alors écrire le tri selection : les facilités de Python on obtient : ... Le principe de construction d'un algorithme récursif est.



Algorithmes de tri.

V. Tri fusion. 1. Présentation du problème. 2. Quelques définitions. 3. Calcul de la médiane. Trier une liste ou un tableau à une dimension. En Python :.



Informatique en CPGE (2018-2019) Algorithmes de tri 1 Introduction

Le tri par insertion d'un tableau à n éléments [t0



Trier – Divide and conquer

Fusion de deux listes – Programme Python. Python def fusion(T1T2) : Tri fusion d'une liste – Programme Python. Python def trifusion(T) :.



Algorithmes de tris

?n. 2. ? que l'on trie par un appel récursif puis on fusionne les deux parties triées. partie triée partie triée. – tri des deux moitiés du tableau : fusion.



Leçon 903 : Exemples dalgorithmes de tri. Correction et complexité

Algorithm 1 Algorithme récursif du tri par sélection classique. 1: function Tri-Sélection(A i) > A : tab à trier ; i ? N.



Recursion in Python - University of Calgary in Alberta

3 elements of recursive algorithm •Termination condition –At some point recursion has to stop –For example don’t go beyond leafs •Leafs don’t have children referring to children leafs causes algorithm to crash •Recursive call –Algorithm calls itself on subsets of the input data –One ore more recursive calls



Recursion in Python - University of Calgary in Alberta

Recursion in Python 2 What This Really Means Breaking a problem down into a series of steps The final step is reached when some basic condition is satisfied The solution for each step is used to solve the previous step The solution for all the steps together form the solution to the whole problem (The “Tam” translation) Definition Of

What is tail recursion in Python?

Example: Tail Recursion •Tail recursion: A recursive call is the last statement in the recursive function. •Name of the example program: tail.py def tail(no): if (no

Chapitre 3informatique commune

Algorithmes de tris

1.

Intr oductionOutre l"intérêt intrinsèque que peut représenter le tri des éléments d"un ensemble, il peut être utile, en préalable

à un traitement de données, de commencer par trier celles-ci. Considérons par exemple le problème de la

recherche d"un élément dans un tableau. On sait que ce problème a un coût linéaire, mais si on prévoit de

faire de nombreuses recherches, il peut être intéressant de commencer par trier ces données, car le coût d"une

recherche dichotomique est logarithmique.

L"objet de ce chapitre est donc de décrire les principales méthodes de tri, et de faire l"étude de leur coût.

1.1

Pr ésentationdu pr oblème

Avant toute chose, il importe de prendre conscience que la performance d"un tri va être directement liée à la

structure de données utilisée et en particulier du temps d"accès à un élément : nous savons (cf. le chapitre 1) que

l"accès à un élément d"un tableau est de coût constant contrairement à l"accès à un élément d"une liste chaînée

qui est de coût linéaire. Certains algorithmes peuvent se révéler plus adaptés à l"une de ces deux structures

qu"à l"autre. Les méthodes de tris peuvent aussi différer suivant que la structure de donnée à trier soit mutable

ou pas : dans le cas d"une structure mutable, on cherchera à trier les élémentsen place, c"est à dire sans coût

spatial supplémentaire.

En ce qui nous concerne, nous allons essentiellement nous intéresser aux algorithmes de tris qui procèdent

par comparaison entre les éléments d"un tableau. Nous allons donc considérer un tableaut= [a0;a1;:::;an1]

d"éléments d"un ensemble E muni d"une relation d"ordre4et nous autoriser les seules opérations suivantes :

com parerdeux élémen tsaietajà l"aide de la relation4; perm uterdeux élémen tsaietajdu tableau. Nous supposerons ces deux opérations élémentaires de coûts constants.

Dans la pratique, ces algorithmes seront illustrés enPythonpar le tri d"une liste à valeurs numériques.

Remarque

. Il existe des algorithmes qui n"utilisent pas de comparaison entre éléments mais tirent profit d"une

information supplémentaire dont on dispose sur les éléments à trier. Le tri par base (radix sorten anglais) utilise

la décomposition dans une base donnée des nombres entiers pour les trier. D"autres algorithmes tirent partie de

la représentation en mémoire des objets à trier. Ces algorithmes seront brièvement évoqués dans la dernière

partie de ce chapitre.

Algorithmes stables

Il peut arriver que4soit seulement un pré-ordre total, c"est à dire une relation vérifiant :

-8(x;y)2E2,x4youy4x; -8x2E,x4x; -8(x;y;z)2E3,x4yety4z)x4z;

Mais deux élémentsxetypeuvent vérifierx4yety4xsans avoirx=y(ils sont alors ditséquivalents).

L"exemple le plus courant consiste à trier des couples de valeurs en s"intéressant uniquement à la première

composante de ces couples : la relation : (x;y)4(x0;y0)()x6x0est un pré-ordre total surN2.

On dit d"un algorithme de tri qu"il eststablelorsqu"il préserve l"ordre des indices entre deux éléments équivalents.

Autrement dit, siaietajsont équivalents et sii < j, alors dans le tableau triéaisera toujours placé avantaj.

Nous allons maintenant étudier deux algorithmes de tri élémentaires : le tri par sélection et le tri par insertion,

avant de nous intéresser aux algorithmes de tri les plus performants.

Jean-Pierre Becirspahic

3.2informatique commune

1.2

L etri par sélection Appeléselection sorten anglais, c"est l"algorithme le plus simple qui soit : on cherche d"abord le plus petit

élément du tableau, que l"on échange avec le premier. On applique alors cette méthode au sous-tableau restant.m- recherche d"un élément minimal :

m- permutation avec le premier : mtri- tri du tableau restant :

La description de cet algorithme montre que nous avons besoin d"une fonction qui calcule l"indice du minimum

de la partie du tableau comprise entre les indicesjetn1. Pour des raisons de lisibilité nous allons la rédiger

séparément de la fonction principale.defminimum(t, j): i, m = j, t[j] forkinrange (j+1,len(t)): ift[k] < m: i, m = k, t[k]

returniOn justifie la validité de cette fonction en prouvant par récurrence l"invariant suivant :

à l"entrée de la boucle d"indicek,t[i] =metm= minnt[`]`2~j;k1o.defselect_sort(t): forjinrange (len(t)1): i = minimum(t, j) ifi != j:

t[i], t[j] = t[j], t[i]On justifie la validité de cette fonction en prouvant par récurrence l"invariant suivant :

à l"entrée de la boucle d"indicejle tableaut[0 :j]est trié et8k>j,t[j1]6t[k].

Étude de la complexité

Le nombre de comparaisons effectuées par la fonctionminimum(t, j)est égal àn1jdonc le nombre total

de comparaisons est égal àn2X j=0(n1j) =n(n1)2 n22 et le nombre d"échanges inférieur ou égal àn1.

Il s"agit d"un algorithme de coût quadratique. Une de ses particularités est le nombre réduit (linéaire) d"échanges

effectués. Il peut donc présenter un intérêt sur des données coûteuses à déplacer mais aisément comparables.

Remarque

. Il s"agit d"un algorithme stable à condition, quand il y a plusieurs minimums équivalents, de

permuter le premier rencontré. La version ci-dessus est stable (mais elle ne le serait pas si<était remplacé par

6à la ligne 4 de la fonctionminimum).

1.3

L etri par insertion

Appeléinsertion sorten anglais, il consiste à parcourir le tableau en insérant à chaque étape l"élément d"indicej

dans la partie du tableau (déjà triée) à sa gauche, un peu à la manière d"un joueur de cartes insérant dans son

jeu trié les cartes au fur et à mesure qu"il les reçoit.a jpartie triée- insertion dans un tableau trié : partie triée- tri du tableau restant :

Algorithmes de tris3.3Nous allons commencer par rédiger une fonction qui a pour objet d"insérer l"élémentt[j]dans la partie du

tableaut[0 :j] supposée triée par ordre croissant :definsere(t, j): k = j whilek > 0andt[k] < t[k1]: t[k1], t[k] = t[k], t[k1] k= 1On justifie la validité de cette fonction en prouvant l"invariant : à l"entrée de la boucle d"indicek >0les tableauxt[0 :k]ett[k:j+1]sont triés.

Remarque

. Cette fonction respecte les exigences posées en début de chapitre (on s"autorise uniquement des

permutations entre deux éléments du tableau) mais en contrepartie réalise un nombre inutilement élevé

d"affectations (2p, oùpest le nombre d"éléments det[0 :j]qui sont supérieurs àt[j]). En procédant à un simple

décalage on réduit le nombre d"affectations àp+2 :definsere(t, j): k, a = j, t[j] whilek > 0andt[k] < t[k1]: t[k] = t[k1] k= 1 t[k] = aQuelle que soit la version choisie, la fonction principale s"écrit ensuite : definsertion_sort(t): forjinrange (1,len(t)): insere(t, j)On justifie la validité de cette fonction en prouvant l"invariant : à l"entrée de la boucle d"indicejle tableaut[0 :j]est trié.

Étude de la complexité

Théorème

. -Dans le pire des cas, le nombre de comparaisons et d"échanges du tri par insertion est équivalent àn22.

Preuve.Insérer un élément dans un tableau trié de longueurjnécessite au plusjcomparaisons et échanges

donc en tout n1X j=1j =n(n1)2comparaisons et échanges. Cette situation a effectivement lieu dans le cas où la

liste initiale est triée par ordre décroissant.Théorème. -Le tri par insertion effectue en moyenne un nombre de comparaisons et d"échanges équivalent àn24

Preuve.

On suppose dans ce modèle que la suite des nombres à trier est la suite des entiers1;2;:::;net l"on

admet que toutes les permutations (a1;:::;an) de ces entiers sont équiprobables.

Rappelons qu"uneinversionest un couple(i;j)vérifiant :16i < j6netaj< ai. Chaque permutation supprime

une et une seule inversion et, une fois le tri terminé, il n"y a plus aucune inversion. Ainsi le nombre total

d"échanges effectués est égal au nombre d"inversions dans la permutation initiale, et le nombre de comparaisons

majoré d"au plusn. Calculer le nombre moyen d"échanges dans la procédure de tri par insertion revient donc à

compter le nombre moyen d"inversions de l"ensemble des permutations surnéléments.

Remarquons maintenant que l"image miroir d"une permutationest une permutation0. Il est clair que(i;j)

est une inversion desi et seulement si ce n"est pas une inversion de0. La somme du nombre d"inversions

deet de celles de0est donc égal à n 2! =n(n1)2. On peut donc regrouper deux par deux les termes de la

somme des nombres d"inversions des permutations surnéléments et on obtient ainsi que le nombre moyen

d"inversions sur l"ensemble des permutations est égal à :n(n1)4 .Jean-Pierre Becirspahic

3.4informatique commune

Remarque. Le tri par insertion (tel qu"il est rédigé ci-dessus) est stable. 2.

Algorithmes de tris e fficacesNous venons d"étudier deux algorithmes de tri, tous deux de coût quadratique, aussi bien dans le pire des cas

qu"en moyenne. Peut-on faire mieux? Avant de répondre à cette question par l"affirmative, nous allons chercher

à minorer le coût d"un algorithme de tri par comparaison, en introduisant la notion d"arbre de décision.

2.1

C oûtminimal d"un algorithme de tri

Arbre de décision

Soitn2Nun entier; on désire faire un choix parminpossibilités données dans un ensembleCde cardinaln.

Unarbre de décisionest un arbre binaire tel que : la r acineest étiquetée par C; chacune des f euillesest étiquetée par un singleton incl usdans C;

chaque noeud qui n"est pas une feuille est étiqueté par un sous-ensembleC1deC, et ses deux fils par des

sous-ensembles stricts et non videsC2etC3deC1vérifiant :C1=C2[C3.

De plus, on adjoint à chaque noeud un test booléen; les deux arêtes issues de ce noeud portent respectivement

les labels v (pourvrai) en direction deC2, et f (pourfaux) en direction deC3.

Voici par exemple un arbre de décision permettant de choisir le plus petit parmi trois nombresa,betc:fa;b;cgfa;cgfagv

fcgfv fb;cgfbgv fcgffa < b a < cb < c

L"instruction définie par un noeud d"un arbre de décision est la suivante : on sait que le choix à réaliser se trouve

dans l"ensembleC1. On effectue le test correspondant; si le test est vrai le choix est à réaliser dansC2; sinon il

est à réaliser dansC3.

Un arbre de décision pour un choix dans un ensemble de cardinalndoit posséder au moinsnfeuilles; un arbre

binaire de hauteurhpossédant au plus2hfeuilles, la hauteurhd"un arbre de décision doit vérifier l"inégalité :

2h>n, soith>dlogne.

Tri par comparaison

Un algorithme de tri procédant par comparaison peut être associé à un arbre de décision sur l"ensembleC

desn!permutations possibles des éléments de ce tableau, les tests associés à chacun des noeuds étant une

comparaison entre deux éléments du tableau.

Voici par exemple l"arbre de décision associé au tri par insertion d"un tableau à trois éléments[a;b;c](pour des

raisons de lisibilité, les étiquettes des noeuds non terminaux n"ont pas été représentés) :...

[a;b;c]v [a;c;b]v [c;a;b]ffv [b;a;c]v [b;c;a]v [c;b;a]fffa < b b < ca < c a < cb < c

Algorithmes de tris3.5Sur cet arbre de décision chaque descente dans l"arbre correspond à une comparaison, accompagnée d"une

permutation lorsqu"on se dirige vers le fils droit. De la sorte, il est aisé d"observer que le cas le plus favorable est

celui du tableau déjà trié qui ne nécessite que deux comparaisons et aucune permutation, et que le cas le plus

défavorable est celui du tableau trié à l"envers qui nécessite trois comparaisons et autant de permutations.

Sachant qu"un arbre de décision associé à un algorithme de tri par comparaison possède au moinsn!feuilles, on

en déduit le résultat suivant :

Théorème. -Tout algorithme de tri par comparaison utilise dans le pire des cas au moinsdlogn!ecomparaisons.

Preuve.

La hauteurhde l"arbre de décision vérifie :h>dlogn!e, ce qui signifie qu"il existe au moins une

configuration nécessitantdlogn!ecomparaisons, voire plus.Au prix d"un raisonnement un peu plus délicat, on peut même prouver le :

Théorème. -Tout algorithme de tri par comparaison utilise en moyenne au moinsdlogn!ecomparaisons.

Preuve.

Nous n"allons pas prouver complètement ce théorème mais nous contenter d"un résultat plus faible en

prouvant (par récurrence surf) que dans tout arbre binaire strict àffeuilles, ces dernières ont une profondeur

moyenne supérieure ou égale àlogf. Si atteindre chacune de ces feuilles était équiprobable, nous pourrions

conclure, mais rien ne dit que ce soit le cas.

C" estbien éviden tl orsquef= 1.

Si f >1, supposons le résultat acquis jusqu"au rangf1, et considérons un arbreFàffeuilles.

Puisquef>2, la racine de cet arbre possède un fils gaucheF1contenantf1feuilles et un fils droitF2contenantf2feuilles, avec 16f1, 16f2etf1+f2=f.

La profondeur moyenne des feuilles de cet arbre est donc égale à : h m=1f X x2Fh(x) =1f X x2F1

1+h1(x)+1f

X x2F2

1+h2(x)= 1+1f

X x2F1h

1(x)+1f

X x2F2h 2(x)

oùh(x)désigne la profondeur de la feuillexdansF, eth1(x)eth2(x)la profondeur respectivement dans

F1et dansF2.

Par hypothèse de récurrence on a :

1f kX x2Fkh k(x)>logfk, donchm>1+1f f1logf1+f2logf2. La fonctionx7!xlogxétant convexe, on en déduit :f1logf1+f2logf2>(f1+f2)logf1+f22 , puis : h m>1+logf2 = logf :Corollaire . -Le coût d"un algorithme de tri par comparaison est en moyenne comme dans le pire des cas un (nlogn). Preuve.La croissance de la fonction ln prouve l"encadrement :Z k k1lntdt6lnk6Z k+1 k lntdt.

Sachant que log(n!) =1ln2

n X k=2lnkon en déduit :1ln2 Z n 1 lntdt6log(n!)61ln2 Z n+1 1 lntdt. Le calcul de ces intégrales conduit alors à :nlognn1ln2

6log(n!)6(n+ 1)log(n+ 1)nln2, ce qui prouve

l"équivalent : log(n!)nlogn.

Ce dernier résultat permet envisager l"existence d"algorithmes semi-linéaires pour trier un tableau. Nous allons

en étudier deux dans les sections suivantes.

Jean-Pierre Becirspahic

3.6informatique commune

2.2

L etri fusion Appeléemerge sorten anglais, nous l"avons déjà rencontré comme exemple d"algorithme récursif. Cette méthode

adopte une approche " diviser pour régner » : on partage le tableau en deux parties de tailles respectivesjn2

ketln2

mque l"on trie par un appel récursif, puis on fusionne les deux parties triées.partie triéepartie triée- tri des deux moitiés du tableau :

fusion- fusion des parties triées :

Malheureusement, une difficulté se présente : comment fusionner deux demi-tableaux en place, c"est à dire en

s"autorisant uniquement la permutation de deux éléments dans le tableau? Ce n"est pas impossible à réaliser

mais la démarche est trop complexe pour être intéressante en pratique. C"est pourquoi nous allons déroger à

nos exigences initiales en s"autorisant l"utilisation d"un tableau provisoire pour y stocker le résultat de la fusion.

Ainsi, le schema de l"algorithme de tri fusion devient :partie triéepartie triée- tri des deux moitiés du tableau :

fusion- fusion dans un tableau auxiliaire :quotesdbs_dbs6.pdfusesText_12