[PDF] Algorithmes de tri. V. Tri fusion. 1. Pré





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

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusionAlgorithmes de tri.

Cours N°4.mathieu.gourcy@ac-clermont.fr

PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusionL"ordinateur a l"intelligence de celui qui s"en sert!! PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Présentation du problème

2. Quelques définitions

3. Calcul de la médianeTrier une liste, ou un tableau à une dimension.

En Python :>>>L=[5,2,4,3,1]

L sort print L [1,2,3,4,5] Possible dès lors que l"ensemble de ces objets est muni d"un ordre total : M =['pcsi','psi','mpsi']>>>M.sort() print M

['mpsi','pcsi','psi']Nous allons présenter et comparer ici plusieurs méthodes de tri. A chaque fois :

Principe

Implémentation

Complexité temporelle en évaluantle nombre de comparaisons entre deux élements.PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Présentation du problème

2. Quelques définitions

3. Calcul de la médianeDéfinition 1.1

Un algorithme de tri permet d"organiser une collection d"objets selon un ordre déterminé.

Les objets à trier doivent pour cela faire partie d"une classe munie d"une relation d"ordre. Les relations d"ordre les plus utilisées sont l"ordre numérique et l"ordre lexicographique.Définition 1.2

Un algorithme de tri est diten places"il modifie directement la structure qu"il est en train de trier. Nécessite que l"objet trié soit modifiable. En Python, typiquement une liste. Intérêt principal : complexité en mémoire (ou spatiale) réduite!Définition 1.3 Un algorithme de tri d"une liste est ditstables"il conserve la position relative dans la liste

des quantités qui sont égales pour la relation d"ordre. Exemple : on veut trier la liste de cartesT= [6|;5;4r;5q]

Si le tri laisse le5avant le5q, il s"agit d"un tristable, sinon il estinstable: si une fois trié, on obtient :T= [4r;5;5q;6|], le tri est stable,

si une fois trié, on obtient :T= [4r;5q;5;6|], le tri est instable.PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Présentation du problème

2. Quelques définitions

3. Calcul de la médianePourquoi trier?

Par exemple, pour faire des

recherches ou encore pour déter minerla : Définition 1.4

Médiane.SoitL= [L[0];L[1];:::;L[n1]]une liste triée contenantnéléments.Lorsquenimpair, il existep2Ntel quen=2p+1, la médiane deLest l"élémentL[p]Lorsquenest pair, il existep2Ntel quen=2p, la médiane deLest alors la moyenne

des élémentsL[p1]etL[p]soit :L[p1]+L[p]2 Si la listeLn"est pas triée, la médiane deLest définie comme la médiane de la liste

obtenue à partir deLen triantL.Si on dispose d"unefonction_de_tripour trierL, on pourra ainsi calculer avec Python :

defmediane(L):"""calculel am édianed 'unel isten ont riée"""L=fonction_de_tri(L)# L'affectatione st-ellen écessaire? n=len(L)

if n %2==1: si n =2 p +1 return L n //2] on r envoie L p a vec p n //2 else return

0 .5*(

L n //2-1]+ L n //2]) si n =2 p c 'estl 'autre PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéPrincipe du tri par sélection :comme pour les photos de classe,

on cherche d"abord le plus petit élément du tableau que l"on échange avec le premier.

On applique alors de nouveau cette méthode au sous-tableau restant :recherche (etsélection) d"un élément minimal :m

permutation avec le premier : mT[0]tri du tableau restant : mtableau restant à trier PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéTri par sélection(selection sort) à la main avecT= [8;3;9;6]:8396

3896
3698
3689

Que penser du dernier? D"où l"algorithme....

PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéNous avons d"abord besoin d"une fonction qui calculeiMinl"indice du minimum de la partie

du tableau comprise entre les indicesjetn1. Pour la lisibilité, rédigeons la séparément :

defindice_min(T,j):"""retourl 'indiced um inimumd us oust ableauT [j:]"""mini= j for i i n r ange j +1, len T if T i T mini mini i return m ini Nous pouvons maintenant implémenter facilement le tri par sélection : deftri_selection(T):fork i nr ange(len(T)-1):# l ed erniere lements eraf orcementt rie iMin i ndice_min T k if i Min k A q uoi

ç a

s ert T iMin T k T k T iMin return T Par c ommodité car T m odifié Ce tri est en place et stable. Ainsi implémenté, un appel direct dans la console donnera : t ri_selection ([8,3,9,6]) [3, 6, 8, 9] PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéTerminaison: évidente car deux bouclesforimbriquées.

(une pour tri_selection et une pour indice_min) qui, forcément, terminent. On peut aussi vérifier qu"il n"y a pas de dépassement d"indice ...

Correction.

On justifie la validité de la fonction indice_min(T,j) en prouvant par récurrence l"invariant suivant :

A la fin de la i

èmeitération :T[mini] =min

T[l];l2~j;j+i

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

A la fin de la i

èmeitération(i2N) :T[0:i]est trié ET8k>i;T[k]>T[i1]PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéComplexité.

Il y a une comparaison par itération de la boucle interne (celle de indice_min). Le nombre de comparaisons de données est ainsi avecn=len(T): n2X k=0n1X i=k+11=n2X k=0(n1k) = (n1)2(n1)(n2)2 =n(n1)2 n22 =O(n2) Le nombre de comparaisons est donc constant, que ce soit le pire cas, le meilleur cas, ou le cas moyen.

Synthèse tri par selection :Complexité

meilleur des casO(n2)cas moyenO(n2)pire des casO(n2)Coût quadratique (en terme de comparaisons). Avantage : le nombre réduit d"échangeseffectués (au piren1).

Il présente un intérêt sur des données coûteuses à déplacer mais aisément comparables.

PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexité

Tri par insertion(insertion sort) deT= [8;3;9;6].Pr incipedu jeu de car te: 8396 8396
3896
3896
3896
3896
3689
Pour mettre 6 à sa place, il a fallu successivement décaler vers la droite le 9 puis le 8.

D"où l"algorithme....

PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéLe code Python du tri par insertion peut donc s"écrire :

deftri_insertion(T):fork i nr ange(1,len(T)):# b alayageà p artird u2 emee lement cle T k c le r epresente l a v aleur a i nserer i k i r epresente l 'indiceo ui nsererl ac lewhilei > =1 a ndc le< T [i-1]: # insertiond ansp artiet riee T i T i -1] d ecale v aleurs d 'unr angv ersl ad roitei- =1 T i c le Place t rouvée o n i nsere c le a l 'indicei returnT Comme ce tri se fait en place, lereturn Tde la fin est "facultatif" mais commode. Il permet par exemple de tester directement notre fonction dans la console : t ri_insertion ([8,3,9,6]) [3, 6, 8, 9] PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexité

Terminaison.Le programme termine car :Une boucle for termine toujours.

Dans la boucle while :iest un variant de boucle.

Correction.La preuve nécessite 2 invariants de boucle :un pour la boucle for :

A la fin de la l

èmeitération :8k2~1;l;T[k1]6T[k]un pour la boucle while :

A la fin de la j

èmeitération :8k2~lj;l1;cle Complexité.Le nombre de comparaisons pour un tableau de taillenest :

Au pire :

n1X k=1k=n(n1)2 n22 =O(n2)si liste "inversée"

Au mieux :

n1X

k=11=n1=O(n)si liste déjà triéePSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation

3. Terminaison, correction, complexitéSynthèse tri par insertion :Complexité

meilleur des casO(n)cas moyenO(n2)pire des casO(n2)Remarques.

1Notre tri par insertion est en place : sa complexité en espace mémoire est enO(1).2C"est un tri quadratique (donc peu efficace), cependant, on pourrait démontrer que

dans le cas d"un petit nombre d"éléments à trier, c"est le plus rapide en moyenne (hors

programme).3Il estégalement très efficace lorsque le tab leauest déjà presque tr iécar en O(n).4Ce n"est évidemment pas le cas lorsque le tri doit être effectué sur de grands tableaux

très " désordonnés ». PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation naïve

3. Terminaison, correction, complexité

4. Tri rapide "en place"

Le tri rapide(quick sort) : tri récursif basé sur une méthode "diviser pour régner».

Le principe (

récent ) est le suivant :Choisirarbitr airementdans le tab leauun élément piv otp:p Enlever le pivot de la liste, et segmenter le tableau en deux sous-tableaux l"un contenant les éléments strictement plus petits quep, l"autre les élements restants

supérieurs àp:pRecommencer récursivement avec les tableaux situés à gauche et à droite du pivot,

puis rassembler le tout :triptri PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation naïve

3. Terminaison, correction, complexité

4. Tri rapide "en place"Dans ce cours, le pivotpsera le dernier élément de la liste.

Appliquons cet algorithme récursif à la main avecT= [6;5;2;1;3;4].

On prend pour premier pivot4, on obtient donc :

[2;1;3] [4] [6;5] Puis on prend3comme pivot dans la liste de gauche, et5dans celle de droite : [2;1] [3] [] [4] [] [5] [6]

En continuant ce processus, on obtient :

[] [1] [2] [3] [] [4] [] [5] [6]Exercice d"application 1 Décrire l"algorithme de tri rapide en pseudo-code puis le traduire en une fonction récursive Pythontri_rapide(L)qui renvoie une copie triée de la listeLpassée en argument sans

modifier cette listeL.Ici ce n"est pas un trien placeque nous implémentons...PSI* Lycée La FayetteInformatique. Cours N°4 : Algorithmes de tri.

I. Introduction.

II. Tri par sélection.

III. Tri par insertion.

IV. Tri rapide.

V. Tri fusion1. Principe

2. Implémentation naïve

3. Terminaison, correction, complexité

4. Tri rapide "en place"

Terminaison du tri rapide.

Notonsnla longueur de la liste à trier.Soit(up)la suite des longueurs maximales successives des listes passées en argument de tri_rapide.

Reprenons l"exemple deT= [6;5;2;1;3;4]. On a donc

u

0=6puis, avec l"algorithme :

[2;1;3] [4] [6;5]doncquotesdbs_dbs6.pdfusesText_12