ALGORITHMES DE TRI PDF ALGORITHMES DE TRI Entrée :

Tri par insertion [tr05] - Exercice

Java - Tri par insertion (Solution). Mots-Clés Algorithmes de tris et rangs Tri par insertion ?. Requis Axiomatique impérative (sauf Fichiers) ?.

Les différentes méthodes de tries

IV)Tri par Insertion (insertionSort) . Au 5èmele tableau est trié et l'algorithme s'arrête et on s'aperçoit qu'il y a N-1 ... Implémentation en java :.

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

Java im- plémente ce tri pour des tableau de taille inférieure ou égale à 7. Le tri par insertion séquentiel (Algorithme 4) effectue la recherche de la ...

Algorithmique Trier et Trouver

Tableaux triés algorithmes de tris. 11 de 47. Insertion dans un tableau trié. Algorithme (Insert). Entrées : • Tableau tab

Les algorithmes de tris

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.

Chapitre 14 Les techniques de Recherche et de Tri

Fichier : Search.java ; Méthode linearsearch L'algorithme de tri associé au tri par sélection consiste à trouver l'emplacement du ... Tri par insertion.

ALGORITHMES DE TRI

ALGORITHMES DE TRI Entrée : tableau A[] de données comparables (interface Comparable en Java) ... tri par insertion (insertion sort).

TD n 2 - Correction

Java. Licence Informatique. Année 2005-2006. TD n. ?. 2 - Correction Exercice 2 [Tri par insertion et piles] Écrire un programme de tri par insertion ...

Algorithmes de tri quadratiques en java

8 nov. 2008 Algorithmes de tri quadratiques en java ... 3 Tri insertion ... dichotomique dans un tableau trié a une complexité logarithmique.

Algorithmes de tris

— Dans le pire des cas le nombre de comparaisons et d'échanges du tri par insertion est équivalent à n2. 2 . Preuve. Insérer un élément dans un tableau trié de

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSALGORITHMES DE TRI Tri TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiOn a un fichier d" ´el´ements aveccl ´es comparables- on veut les ranger selon l"or dre les cl

´es

´es comparables :

public interface Comparable int compareTo(T autre_objet); x.compareTo(y)est n´egatif sixpr´ec`edey, ou positif sixsuitydans l"ordre "naturel»des´el´ements Tri inter ne : tout le fichier est en m

´emoire

(repr ´esent´e par un tableau ou une liste chaˆın´ee) Tri exter ne : fichier stock ´e partiellement ou enti`erement en m´emoire externe (disque) - acc `es`a m´emoire externe est couteux...

Tri interne

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiiEntr

´ee : tableauA[]de donn´ees comparables (interfaceComparableen Java)

On veut trier le tableau

Solutions :

tri par s´election (selection sort) tri par insertion (insertion sort) tri par fusion (Mergesort) tri par tas (Heapsort) tri rapide (Quicksort)

Tri (cont)

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiiitableauA[1::n]

Tri par s

´election :

pouri 1;:::;n1faireA[1::i]contient lesi´el´ements les plus petits deA, tri

´es

Tri par insertion :

pouri 2;:::;nfaireA[1::i]contient lesipremiers´el´ements deA, tri´es

Tri par s

´electionTRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSivAlgoTRI-SELECTION(A[1:::n])

S1pouri 1;2;:::;n1faire

S2minidx i

S3pourj i+ 1;:::;nfaire

S4siA[j]< A[minidx]alorsminidx j

//(maintenantA[minidx] = minfA[i];:::;A[n]g) ´e comparaison d" ´el´ements [ligne S4](n1) + (n2) ++ 1 =n(n1)2 fois; echange d"´el´ements [ligne S5](n1)fois

Temps de calcul :(n2)pour toutA

mais pas n ´ecessairement une mauvaise id´ee si l"´echange est beaucoup plus couteux que la comparaison

Tri par insertion

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSvAlgoTRI-INSERTION(A[1::n])

I1pouri 2;:::;nfaire

I2j i1

I3tandis quej1etA[j]< A[i]faire

´echangerA[i]$A[j]

I5j j1Complexit

´e - d´epend de l"ordre des´el´ements au d´ebut meilleur cas (d ´ej`a tri´e) :n1comparaisons et aucun´echange pire cas (tri

´e en ordre d´ecroissant) :n(n1)2

comparaisons et´echanges moyen cas :(n2) tr `es utile siAest"presque tri´e»au d´ebut g ´enie algorithmique : min enA[1](sentinelle) - pas de testj1en I3 remplacer

´echange par d´ecalage en I4

Tri par tas

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSviHEAPSORT(A)// vecteur non-tri´eA[1::n]

H1heapify(A)

H2pouri jAj;:::2faire

´echangerA[1]$A[i]

H4 S OMBRER(A[1];1;A[1::i1])A[1::n]est dans l"ordre d´ecroissant`a la fin (pour l"ordre croissant, utiliser unmax-tas) TempsO(nlogn)dans le pire des cas, sans espace additionnelle! quicksort:O(n2)dans le pire des cas mergesort:O(nlogn)dans le pire des cas mais utilise un espace auxiliaire de taillen

Tri par fusion

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSviiAlgoMERGESORT(A[1::n])

M1sin <2alors retournerA

M2B1 TRI-FUSION(A[1::bn=2c])

M3B2 TRI-FUSION(A[bn=2c+ 1::n])

M4B FUSION(B1;B2)

M5retournerB

Fusion de deux tableaux

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSviii1Entr´eeA[1::n],B[1::m](de typeComparable[]) 2 intialiser C[1::n+m]

3i 1;j 1

4pourk 1;2;:::;n+mfaire

5sij > mouA[i]B[j]alorsC[k] A[i];i i+ 1

6sinonC[k] B[j];j j+ 1Temps de calcul :(n+m)affectations, et(n+m1)comparaisons (au pire)

Tri par fusion - analyse

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSixThm.En tri par fusion, le nombre de comparaisons est inf´erieur`aC(n) =

ndlgne. (n >0) Preuve. Nombre total de comparaisons sur chaque niveau de r´ecurrences estn

Nombre total de niveaux de r

´ecurrences :dlg(n)e.

Nombre d"affectations :ndlgne.

Complexit

´e(nlogn)mais on a besoin d"un espace auxiliaire de taillenpour la fusion (quand le tableau est"presque tri´e», tri par insertion est plus rapide!)

Tri rapide

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSx1.choisir un´el´ement (pivot), le placer dans sa case finale i, mettre tous les´el´ements

inf

´erieurs enA[1::i1]et tous les´el´ements sup´erieurs enA[i+ 1::n]428135172689pivot = 5428135172689422135178689422135978681422139578681échangeréchangerfin de balayer

remettre le pivot2.trierA[1::i1]etA[i+ 1::n](r´ecurrence)

Tri rapide (cont)

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiTemps de calcul :(nlogn)en moyen si le pivot est bien choisi;(n2)en

pire cas

Choix du pivot : m

´ediane de trois (A[1],A[n1]etA[n]) ou al´eatoire (uniforme) g

´enie algorithmique :

1. tri par insertion quandnest petit (5::20)

2. ne pas ex

´ecuter les r´ecursions sur les petits sous-tableaux, mais plutˆot faire un tri par insertion une fois `a la fin

Tri rapide - analyse

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiD

´ef.SoitD(n)le nombre moyen de comparaisons avec un pivot al´eatoire, o`un est le nombre d"

´el´ements dans un tableauA[1::n].

On va d

´emontrer queD(n)n

2O(logn).

Lemme.On aD(0) =D(1) = 0, et

D(n) =n1 +1n

n1X i=0

D(i) +D(n1i)

=n1 +2n n1X i=0D(i): Preuve.Supposons que le pivot est lei-`eme plus grand´el´ement deA. Le pivot est compar ´e`a(n1)autre´el´ements pour la partition. Les deux partitions sont de tailles(i1)et(n1i). Or,iprend les valeurs1;2;:::;navec la mˆeme probabilit

´e.

Performance moyenne (cont.)

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiiPar le lemme pr

´ec´edent,

nD(n)(n1)D(n1) = n(n1) + 2n1X i=0D(i) (n1)(n2) + 2n2X i=0D(i) = 2(n1) + 2D(n1): D"o `u on a

D(n)n+ 1=D(n1)n

+2n2n(n+ 1)=D(n1)n +4n+ 12n

AvecE(n) =D(n)2n+1, on peut´ecrire

E(n) =E(n1) +2n+ 1:

Performance moyenne (cont.)

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxivDonc,

E(n) =E(0) +22

+23
++2n+ 1

D(0)21

+ 2(Hn+11) = 2Hn+14 o `uHn=Pni=11=iest len-i`eme nombre harmonique.

En retournant

`aD(n) = 2 + (n+ 1)E(n), on a alors

D(n) = 2(n+ 1)Hn+14n2<2nHn+1

Donc le nombre de comparaisons en moyenne est tel que D(n)n <2Hn+12O(logn):

En fait, on aD(n)=n <2lnn1:39lgn.

quotesdbs_dbs6.pdfusesText_12

[PDF] ALGORITHMES DE TRI ALGORITHMES DE TRI Entrée :

´es

´es comparables :

´emoire

Tri interne

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSiiEntr

On veut trier le tableau

Solutions :

Tri (cont)

Tri par s

´election :

´es

Tri par insertion :

Tri par s

S1pouri 1;2;:::;n1faire

S2minidx i

S3pourj i+ 1;:::;nfaire

S4siA[j]< A[minidx]alorsminidx j

Temps de calcul :(n2)pour toutA

Tri par insertion

I1pouri 2;:::;nfaire

I2j i1

I3tandis quej1etA[j]< A[i]faire

´echangerA[i]$A[j]

I5j j1Complexit

´e en ordre d´ecroissant) :n(n1)2

´echange par d´ecalage en I4

Tri par tas

H1heapify(A)

H2pouri jAj;:::2faire

´echangerA[1]$A[i]

Tri par fusion

M1sin <2alors retournerA

M2B1 TRI-FUSION(A[1::bn=2c])

M3B2 TRI-FUSION(A[bn=2c+ 1::n])

M4B FUSION(B1;B2)

M5retournerB

Fusion de deux tableaux

3i 1;j 1

4pourk 1;2;:::;n+mfaire

5sij > mouA[i]B[j]alorsC[k] A[i];i i+ 1

6sinonC[k] B[j];j j+ 1Temps de calcul :(n+m)affectations, et(n+m1)comparaisons (au pire)

Tri par fusion - analyse

Nombre total de niveaux de r

´ecurrences :dlg(n)e.

Nombre d"affectations :ndlgne.

Complexit

Tri rapide

Tri rapide (cont)

Choix du pivot : m

´enie algorithmique :

1. tri par insertion quandnest petit (5::20)

2. ne pas ex

Tri rapide - analyse

TRI?IFT2015 H2009?UDEM?MIKL´OSCSUR¨OSxiiD

´el´ements dans un tableauA[1::n].

On va d

´emontrer queD(n)n

2O(logn).

Lemme.On aD(0) =D(1) = 0, et

D(n) =n1 +1n

D(i) +D(n1i)

´e.

Performance moyenne (cont.)

´ec´edent,

D(n)n+ 1=D(n1)n

AvecE(n) =D(n)2n+1, on peut´ecrire

E(n) =E(n1) +2n+ 1:

Performance moyenne (cont.)

E(n) =E(0) +22

D(0)21

En retournant

D(n) = 2(n+ 1)Hn+14n2<2nHn+1

En fait, on aD(n)=n <2lnn1:39lgn.