Introduction à lalgorithmique et la complexité (et un peu de CAML PDF

TP 7 Algorithmes de tri

Le tri à bulles est un algorithme de tri classique. Son principe est simple et il est très facile à implémenter. On considère un tableau de nombres T

Chapitre 4 : Les algorithmes de tri

8.5 – Tri à bulles. • Optimisation de l'algorithme (si temps suffisant). – Après avoir traité i-1 éléments (1 ≤ i ≤ n). • Les éléments de 1..i-1 sont triés.

Complexité (tri à bulle)

La complexité d'un algorithme est la fonction mathématique qui décrit en fonction de la taille des données d'entrées (par exemple le nombre de mots)

Vous avez dit trier ? 1 - algorithmes simples

tri d'un jeu de cartes le tri à bulle dont le principe est assez simple

Algorithmes de tri interne [tr] (3) Méthodes par échanges

Une méthode naıve conduit `a l'algorithme du « tri bulles ». Une autre bulle puis `a trier récursivement un tableau de n−1 éléments. Si C(n) désigne le ...

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

Algorithm 3 Algorithme du tri par dénombrement. 1: function Tri-Bulle(A). > A : tableau à trier. 2:.

LIFAP3 : Algorithmique et programmation procédurale

Le tableau est donc bien trié de 0 à n-1 (et il ne reste rien à trier) ce qui prouve que l'algorithme de tri est correct. Tri à bulles. Le tri à bulles est un

fiche-tri-selection-bulles-insertion.pdf

Ce critère est en effet une relation d'ordre total sur les éléments à trier. La conception d'un algorithme de tri dépend du support matériel de la séquence de

ALGORITHMES DE TRI

- Algorithme de tri par insertion. Pour terminer pour aller plus loin

[PDF] Chapitre 4 : Les algorithmes de tri

tableau vide est trié – tableau ne contenant qu'un seul élément est trié important cet algorithme requiert Le principe du tri à bulles (bubble

[PDF] Leçon 903 : Exemples dalgorithmes de tri Correction et complexité

Algorithm 3 Algorithme du tri par dénombrement 1: function Tri-Bulle(A) > A : tableau à trier 2:

[PDF] Les algorithmes de tris - LIP6

Quelques algorithmes de tris Tris élémentaires Tri par insertion Tri par sélection Tri par permutation Tris avancés Tri Fusion Tri rapide Blin Lélia

[PDF] Méthodes de tri - Kitebnet

La conception d'un algorithme de tri dépend du support Remarque: Dans le pire des cas le tri à bulles fait (n- 1)+(n-2)+ +2+1 comparaisons et autant

[PDF] Sorting Algorithms - Infoscience

Les algorithmes de tri présentés dans ce document sont soit : - élémentaires : tri à bulles tri par sélection tri par insertion et tri par shell

[PDF] Les algorithmes de tri - Luc Brun

Les algortihmes de tri Définition d'un algorithme de tri Le tri par minimum successifs Le tri a bulles Le tri rapide Les algorithmes de recherche

[PDF] Complexité (tri à bulle) - limsi

La complexité d'un algorithme est la fonction mathématique qui décrit en fonction de la taille des données d'entrées (par exemple le nombre de mots)

[PDF] Algorithmes de tri interne [tr] (3) Méthodes par échanges - Unisciel

Tout le probl`eme réside dans le choix des éléments ix et jx `a permuter Une méthode na?ve conduit `a l'algorithme du « tri bulles »

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Introduction à l"algorithmique

et la complexité(et un peu de CAML)

Algorithmes de Tri (et leur complexité)

Nicolas Nisse

Université Côte d"Azur, Inria, CNRS, I3S, France Cours dispensés en MPSI (option Info) au CIV, depuis 2011-

N. Nisse

Algorithmes de Tri 1/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 2/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Tri parselectiondes éléments d"un tableau

Étant donné

un tab leauT= [t0;;tn1]d"éléments d"un ensemble ordonné (disons d"entiers),

on veut modifier la position des éléments dansTtel, qu"à la fin, les éléments deTsoient

ordonnés (e.g., du plus petit au plus grand) ( tri sur place

).Algorithme par Sélection:cf. Slide 12 Chap. 2(fonction "Echange" : slide 17, Chap. 1).Complexité: Doub leboucles imbr iquées.

Notons quec(Echange) =O(1). Donc,

c(triSelection) =

O(1)+n2å

i=0(O(1)+n1å

j=i+1O(1)) =O(n2).Déterminer la complexité d"un algorithme consiste à compter le nombre "d"opérations

élémentaires" réalisées. Ici, on peut se dire que ce qui compte c"est le nombre de "déplacements" des éléments dans le tableau (c-à-d, le nombre d"exécutions de Si une "opération élémentaire" est définie comme un tel déplacement : Quelle est la complexité de l"algorithmetriSelectionappliqué au tableau[j1;2;3;;nj]? Montrez que le pire cas a lieu pour le tableau[jn;n1;n2;;1j] Souvent (dans ce cours), ce qui importe pour le tri est le nombre de compar aisonseff ectuées

N. Nisse

Algorithmes de Tri 3/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 4/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Tri parinsertiondes éléments d"un tableauAlgorithme par Insertion :Initialement, vous tenez toutes vos cartes (non triées)

dans votre main droite. À chaque étape, vous prenez la "première" (la plus à gauche) carte qui se trouve dans votre main droite, et l" insérez"à sa place"dans v otremain

gauche. À la fin, vos cartes sont triées par ordre croissant dans votre main gauche !!Rappel: fonction "Echange" (slide 17, Chap 1).

Terminaison :

preuv elaissée au lecteur .

Correction :

Un in variantde boucle est "après l"itér ationi, le sous-tableau[jt:(0);;t:(i)j]est ordonné"

À prouver par récurrence suri.

Complexité :

Le nombre d"applications de "Echange" est

c(triInsertion) =O(n1å i=1i1å j=0O(1)) =O(n2). Un pire cas estt= [jn;n1;n2;;1j].N. NisseAlgorithmes de Tri 5/12 Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 6/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Tri à bullesAlgorithme de tri à bulles :comparer répétitivement les éléments consécutifs d"un

tableau, et à les permuter lorsqu"ils sont mal triés. (voir animation sur

Wikipedi a

Intuitivement, on fait "remonter" (comme des bulles) les éléments les plus grands jusqu"à ce qu"ils atteignent leur place.Rappel: fonction "Echange" (slide 17, Chap 1).

Terminaison :

preuv elaissée au lecteur .

Correction :

Un in variantde boucle est "après l"itér ationi, le sous-tableau[jt:(i);;t:(n1)j] contient lesniplus grands éléments det qui sont ordonnés"

À prouver par récurrence (descendante) suri

Complexité :

Le nombre d"applications de "Echange" est

O(n2).

Un pire cas estt= [jn;n1;n2;;1j].N. NisseAlgorithmes de Tri 7/12 Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 8/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Tri Fusion ("merge sort"en anglais)

Pour changer, nous trions ici unelisteet les algorithmes sont présentés sous forme récusive.Algorithme de tri fusion :Divisons notre liste`= [u0;;un1]en deux. Trions

(récursivement) les listes`1= [u0;;u(n1)=2]et`2= [u(n1)=2+1;;un1]. Fusionnons les listes triées`1et`2de façon à obtenir une nouvelle liste`0contenant les éléments de`triés."divise" prend une liste`de longueurnet crée 2 nouvelles listes de longueurdn=2eetbn=2ccontenant les éléments de`. fusion " prend 2 listestriéeset rassemble leurs éléments dans une nouvelle liste triée. tri_fusion " prend une liste et, en utilisant les fonctions précédentes, crée une nouvelle liste contenant les éléments de`triés.

Terminaison :

preuv epar récurrence laissée au lecteur .

Correction :

preuv epar récurrence laissée au lecteur .Exercices :transposez ces algorithmes : sous forme itérative, pour trier des tableaux.

N. Nisse

Algorithmes de Tri 9/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Complexité du Tri Fusion

Nous nous intéressons principalement au nombre de comparaisons des éléments de la liste (i.e,

"opération élémentaire" = comparaison

Divise :Soitcd(n)la complexité de "divise" appliquée à une liste de longueurn. Alors,cd(0) =Xet

c d(n) =X+cd(n2)avecX=0 si on ne compte que les comparaisons etX=O(1)si on compte

aussi la création/l"ajout d"un élément dans une liste. Donc, par récurrence,cd(n) =0 oucd(n) =n=2

=O(n)selon ce que l"on compte (le choix de ce que l"on compte n"aura pas d"influence sur la suite).

Fusion :Soitcf(n1;n2)la complexité de "fusion" appliquée à 2 listes de longueurn1etn2. Alors,

c f(0;0) =cf(n1;0) =cf(0;n2) =O(1)etcf(n1;n2)O(1)+maxfcf(n11;n2);cf(n1;n21)g. On en déduit, par récurrence,cf(n1;n2) =O(n1+n2).

Tri_fusion :Soitc(n)la complexité de "tri_fusion" appliquée à une liste de longueurn. Alorsc(0) =c(1) =O(1)

etc(n) =cd(n)+c(dn=2e)+c(bn=2c)+cf(dn=2e;bn=2c)(application de "divise" à`, puis 2 applications de "tri_fusion" aux listes`1et`2résultantes, de longueurdn=2eetbn=2crespectivement, et enfin "fusion" des 2 listes triées obtenues) . La façon de résoudre une telle suite est présentée ci-dessous. Posonsuk=c(2k). On au0=O(1)etuk=2uk1+O(2k). Soitvk=uk2 k. Alors,v0=O(1)etvk=vk1+O(1). Donc, par

récurrence,vk=O(k). On en déduituk=O(k2k). Pour conclure, pour toutn2N, soitk2Ntel que 2k1

prouvez quec(n)uk=O(k2k). Ainsi,c(n) =O(k2k) =O(nlogn).L"algorithme de Tri_fusion réaliseO(nlogn)comparaisons pour trier une liste de longueurn.Peut on faire mieux ?

N. Nisse

Algorithmes de Tri 10/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 11/12

Tri par SélectionT ripar Inser tionT rià Bulles T riFusion F airemieux ?

Faire mieux que le Tri Fusion ?

Soittabun tableau denentiers à trier. Supposons que les éléments detabsontk2N.Les peuves de terminaison et de correction de cet

algorithme sont laissées au lecteur. Sa complexité estO(n+k). Il a donc une meilleure complexité que Tri_fusion sik=o(nlogn), mais il demande la connaissance d"une bor nesupér ieure sur les

éléments det.

De plus,

en espace , il crée un tableau de taillekqui, si n=o(k), est plus coûteux que l"espace nécessaire à

Tri_fusion.Sans information sur les éléments detab, l"algorithme de Tri_fusion est optimal dans le pire cas.Intuition de Preuve :On suppose quetab= [jt1;;tnj]contient des éléments distincts deux-à-deux.

Triertabrevient à trouver la permutationp: [1;n]![1;n]telle que le tableautab0= [jtp(1);tp(2);;tp(n)j]est trié, i.e., pour

tout 1iLe nombre de permutationsp: [1;n]![1;n]estn!nn.

Soient 1i quetp(i)>tp(j). Il y a une bijection (laissée au lecteur) de1vers2. Doncj1j=j2j= (n1)!=2.

Autrement dit, effectuer une comparaison permet donc de diviser le nombre de permutations candidates par 2.

Trier notre tableau revient à faire des comparaisons jusqu"à ne laisser qu"une unique permutation candidate.

Soit xle nombre

minimum de comparaisons , il doit satisfaire :n!=2x1. Donc, à la louche,nn2x. En prenant le logarithme, on a donc nlognx= #min de comparaisons:N. NisseAlgorithmes de Tri 12/12quotesdbs_dbs20.pdfusesText_26

[PDF] Introduction à lalgorithmique et la complexité (et un peu de CAML

Introduction à l"algorithmique

Algorithmes de Tri (et leur complexité)

Nicolas Nisse

N. Nisse

Algorithmes de Tri 1/12

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 2/12

Tri parselectiondes éléments d"un tableau

Étant donné

Notons quec(Echange) =O(1). Donc,

O(1)+n2å

N. Nisse

Algorithmes de Tri 3/12

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 4/12

Terminaison :

Correction :

À prouver par récurrence suri.

Complexité :

Le nombre d"applications de "Echange" est

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 6/12

Wikipedi a

Terminaison :

Correction :

À prouver par récurrence (descendante) suri

Complexité :

Le nombre d"applications de "Echange" est

O(n2).

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 8/12

Tri Fusion ("merge sort"en anglais)

Terminaison :

Correction :

N. Nisse

Algorithmes de Tri 9/12

Complexité du Tri Fusion

N. Nisse

Algorithmes de Tri 10/12

Outline1Algorithme de Tri par Sélection

2Algorithme de Tri par Insertion

3Algorithme de Tri à Bulles

4Algorithme de Tri Fusion

5Au delà du Tri Fusion

N. NisseAlgorithmes de Tri 11/12

Faire mieux que le Tri Fusion ?

éléments det.

De plus,

Soit xle nombre