[PDF] Algorithmes de tri quadratiques en java

View - Download Algorithmes de tri quadratiques en java

Previous PDF

Next PDF

Algorithmes de tri

Algorithmique 1

Stéphane Grandcolas

Aix-Marseille Université

2021-2022

Contact :stephane.grandcolas@univ-amu.fr

Tris. I

Arbre de décision: tri par insertion.

I Complexité des tris par comparaison dans le pire des cas : borne minimale. I

Tri rapide.

I

Tri par dénombrement,tri par base.

Tris. organiser un ensemble d"objets s elonun o rdredéterminé relation d"ordre: comparaison declés dans nos exemple nous confondrons les objets avec leurs clés I tri par compa raison versus tri pa r indexation I tri sur place : espa cemémoire de tail leconstante I tri stabl e : p réservel"o rdreinitial en cas d"é galité

Quelques tris classiques.

1. Tris enO(n2).

I tri à bulles, I tri par insertion, I tri par sélection.

2. Tris enO(nlogn).

I tri par fusion, I tri par tas, I tri rapide (mais enO(n2)dans le pire des cas).

3. Tris spéciaux.

I tri shell (probablementO(n1:25)), I tri par dénombrement (O(n)). Tri par insertionpartie non triéeipartie triée xPrincipe :insérer les éléments les uns après les autres dans la partie triée Tri par insertionpartie triéeipartie non triée xPrincipe :insérer les éléments les uns après les autres dans la partie triée Insertion :recopie des éléments plus grands vers la droite

Tri par insertion

procédure TRI_PAR_INSERTION(T[1;:::;n]) début pouri:=2jusqu"ànfaire j:=i, tant que((j>1)et(T[j]PERMUTER(T,j,j1), j:=j1, fin faire fin faire fin procédure

Tri par insertion

Pire des cas :i1 permutations à chaque passage.

T(n) =nX

i=2(k1+k2(i1)) =O(n2)

Meilleur des cas :aucune permutation (mais une

comparaison).

T(n) =nX

i=2k=O(n)

Nombre d"inversions

Inversion :(i;j)tel queiT[j]

7 inversions153 11 8 12 7 21 19I

suite triée : 0 inversions I suite triée dans l"ordre décroissant :n(n1)=2 inversions

Nombre d"inversions

Permutation de deux éléments consécutifs inversés :i+1 bi an 3 n

1n2nb inversions=n1+n2+n3+nbInv(i)+ nbInv(i+1)+ 1

Nombre d"inversions

Permutation de deux éléments consécutifs inversés :a i+1 bin 3 n

2n1nb inversions=n1+n2+n3+nbInv(i)+ nbInv(i+1)

Nombre d"inversions

Permutation de deux éléments consécutifs inversés :a i+1 bin 3 n

2n1nb inversions=n1+n2+n3+nbInv(i)+ nbInv(i+1)

En permutant deux éléments successifs non ordonnés on diminue de 1 le nombre d"inversions

Arbre de décision d"un tri.

I tris par comparaison I comparaison!décisionde permuter ou non Arbre de décision :représente tous les scénarios possibles pour une suite denvaleurs. Branche :la suite de permutations faites par le tri pour produire la séquence ordonnée

Arbre de décision du tri par insertion.c acb a

b c a bc ac a ba c ba c bcba b > c ba cbacb a b 321
a <= b a > b a <= c a > cb <= c b > c a <= c a > c b <= cc

Tri par comparaison)arbrebinaire

Arbre de décision du tri par insertion.c acb a

b c a bc ac a ba c ba c bcba b > c ba cbacb a b 321
a <= b a > b a <= c a > cb <= c b > c a <= c a > c b <= cc nombre de feuilles = nombre de branches =n! (1) On peut composern!suites différentes à partir denvaleurs différentes.

(2) On ne peut pas trier deux suitesuetvqui diffèrent par le rang de certains éléments avec la même

séquence de permutations: si9i;jtels queuivj, alors(i)< (j)et(i)> (j).

Complexité des tris par comparaison

Nombre de feuilles :n!

hauteur de l"arbre de décision : h(n)log(n!)orn!vp2nne n(formule de Stirling) donc h(n)logne n=n(lognloge)nlogn

Complexité des tris par comparaison

Nombre de feuilles :n!

hauteur de l"arbre de décision : h(n)log(n!)orn!vp2nne n(formule de Stirling) donc h(n)logne n=n(lognloge)nlogn

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),

4TRI_RAPIDE(T;g;m1),

5TRI_RAPIDE(T;m+1;d),

I tri par comparaisonsen place, I tableau indexé, I le plus rapide dans le cas général, I très utilisé

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),

4TRI_RAPIDE(T;g;m1),{ m1

5TRI_RAPIDE(T;m+1;d),{ m+1>g}

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),

4TRI_RAPIDE(T;g;m1),{ m1

5TRI_RAPIDE(T;m+1;d),{ m+1>g}

Partition :11 23 1417134 26 7112317 4 8 1413 2 9 7 6

98pivotpivotg

g m d d pivot

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),

4TRI_RAPIDE(T;g;m1),

5TRI_RAPIDE(T;m+1;d),826 79 823 141713

112317 4 8 1413 2 9 7 6

4 2 7 9 8 1317 14

2 7 8 13 174

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),O(n)

4TRI_RAPIDE(T;g;m1),T(n=2)

5TRI_RAPIDE(T;m+1;d),T(n=2)

Dans le meilleur cas

T(n) =1+n+2T(n=2) =O(nlogn)

Tri rapide (quick sort)

fonctionTRI_RAPIDE(T;g;d)1si(g2ChoisirpivotdansT[g;:::;d],

3m:=PARTITIONNER(T;g;d;pivot),O(n)

4TRI_RAPIDE(T;g;m1),T(0)

5TRI_RAPIDE(T;m+1;d),T(n1)

Dans le pire des cas

T(n) =1+n+T(n1) =O(n2)

Partition typedrapeau

Après la partition :d

=pivotpivotg

Partition typedrapeau

Pendant la partition :g

=pivotx >pivotéléments en attented

Partition typedrapeau

cas 1 :x>pivot: permutation avec le dernier en attented =pivotgd =pivotx >pivotpivotxi i g

Partition typedrapeau

cas 2 :x=pivot: extension de la zoneid =pivotgd =pivotx >pivotpivotxi g

Partition typedrapeau

cas 3 :xpivotpivot=pivotxi i g

Partitionrapidepivot

1123 4 8 13 2 9 12 6710g

18 17 14d

11Recherche d"un élément plus grand que le pivot à gauche,

et d"un élément plus petit à droite

Partitionrapidepivot

1123 4 8 13 2 9 12 6710g

18 17 14d

11ijpivotpivotà gauche :stoppe avecxipivot

à droite :stoppe avecxjpivot

)permutationdexietxj

Partitionrapidepivot

1123 4 8 13 2 9 12710g

18 17 14d

6

11Extension des zones

Partitionrapidepivot

1123 4 8 13 2 9 12710g

18 17 14d

6

11Recherche d"un plus grand à gauche et d"un plus petit à droite

Partitionrapidepivot

114 8 13 2 12710g

18 17 14d

6119

23Permutation et extension des zones

Partitionrapidepivot

114 8 13 2 12710g

18 17 14d

6119

23Recherche d"un plus grand à gauche et d"un plus petit à droite

quotesdbs_dbs21.pdfusesText_27

[PDF] algorithme de tri par insertion pdf

[PDF] algorithme de tri par sélection

[PDF] algorithme de tri par selection en c

[PDF] algorithme de tri par selection java

[PDF] algorithme de tri par selection pdf

[PDF] algorithme de tri par selection recursive

[PDF] algorithme de tri pdf

[PDF] algorithme de tri rapide

[PDF] algorithme du plus court chemin

[PDF] algorithme du plus court chemin dans un graphe

[PDF] algorithme du plus court chemin java

[PDF] algorithme du plus court chemin python

[PDF] algorithme et langage c

[PDF] algorithme et programmation

[PDF] algorithme et programmation en language c