0 évaluation0% ont trouvé ce document utile (0 vote) 45 vues9 pagesAlgorithmes de Tri
Copyright
© © All Rights Reserved
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
(CHAPITRE
ALGORITHMES DE RECHERCHE}
ET DE TRI
Introduction
Un tablenw est ne liste dont les valeurs ont routes
‘de meme ope.
‘Les algorthmes de recherche consistent vriier
existence d'un ou de plusieus éléments,
satisfisont une condition donnse, dans un tablew,
Les algorithmes de ei consistent & ordonner tes
léments d'un tableau dans Vordce croissant ou
décrossant.
As Algorithmes de recherche
‘= Les deus algorthmes de recherche ls plus connus sont
1. Larecherehe quent
2 Lareherhe dichotomique (le tableau dl tre rg)
[
1- Recherche séquentielle
Principe
(on se propose derechercher un climentx dans un bleao
on compare 'lément eecherehé x & 110}, 8 TUN, 4 TI2),
jusqu’ & ce gun le wouve ou bien ta fin du ubleaw est
aint sven my igure pas Recherche séquentielle
serche_sequentielie (7)
or ke dm range len(¥)
Sexe TK)
return False
+ Dewaidme version
‘Get recherche_sequentieile 3)
for y int Sinon
a one richechr dan le moi drt one lev eT)
Feturir Tove + Ce process et rip jag ce qu'on ose wn soutbleou
seturn (seul len
2- Recherche dichotomique
Pansies
+ Cetalgoritime suppose qe e tableau ex ie
+ Goniste & diver an leas de ale m ox dows pares et 8
‘compare la valeur veherhde avec Ulément stad ex mili di
{ables (lient median.
Size] alos
leprogramne Fate eet ound
Sinon
it < Tia) Alor
‘ova rechrcher dn amet gocher 0) Ti}
Recherche dichotomique : exemple
* Conicon te wien T=. 3,5,6,79,
1 Sto he es ine #8
Recherche dichotomique : exemple
seer A mae ichotomie dans un tableau trie
8 Le tbteaw et upprd i dans
B- Algorithmes de tri
)
Bt | see recherche dichoeonicuetxsH 41 exe plusieurs algoitimes conus pout wet es ements
sey ess ‘isa Sun tblesn
f= ten ttt aes
eee Let per section
= GEE/12 see ite nn mt ~Letripainsrtion
i Seem Ral ~ Lewitt
ous xe tel -
pee sec 1 Danse sited cours, ler ser ect dans Verde craisant
‘Tri par sélection’ Tri par sélection
Le i pur secon conse 4 coqe tape rier le + Psp
‘stm pri es ements na sept le placer ete es
eons snes, mes
1 Surn bleu T dem ements (mts d 0 8) le pracipe
ftlesuvon
= ce
eps eth ten ny ingens
= cere ht pei mente a prin do Ble ene pie
helene el techn se U
~ cuca ee ptt tent de apr len opie
forcerinbted ele Fecanger eT}.
fen jug equ ees wot erent
“Pourehaguet
1 écoulement deporte non ie
Trosver le minimum del pte non rite
1 Echungerte J eemen depose nn ride Tove le min
Pasemiee Parente
ona eran
Permutation Tri par sélection
seven: = GT TST)
~ figs eee ae pe nes de, OF
A-CbD)
~ amc eee ha pe cm te pe
ad
‘Tri par sélection d’un tableau T
fer 4 in range (o-
pains t
for jin range(i+1.n):
se T(3]!
ostor
a
GREAT > Ts)
2 Tri par insertion
Cet algorte consist & were contenu dune se comme pour
tn jeu de cartes. On ft comme tes elements ter Euiet
ons un pa
~ Le premier eéneet comtitu, & ai ou sou, we tte te de
leagues
= Oo rege eat e seco men pour aac te ite ibe de
Tenge 2
= Tus ov rang le woisitne element pou sor uae ie ke de
Tongues
Le priacpe duu pr isenton et done instr 3 Ia ion
Je ements boote plice dans ls peton de tba TDi]
aij wie
‘Tri par insertion
~ Uateoner tment Th iis ns panne
Decl snes spn 4 T] verse
laser ent Ti dane parece,
i —
Inseron “—
4
steemple: GBS]
‘Tri par insertion
‘Tri par insertion d'un tableau T
dee tei_insertiont
pelentt)
for 4 Sn rango(tia):
“std
ee
3- Tria Dulles (Devoir libre)
© LAE: comme pour es deux algoritimes 60 ti
recédeas:
1 Principe
2. Exemple
Tes & Bukbs’
deg xc) - belles)
i Pont)
wrk yor?
acnenage Forse
a.
#6 LCF LCA}
LUD Lad = La CY
enna = Thane
ig echamg == Fake t
Fetes L
yeien
Takara L Eusien
des fusion (M,N) 2
FeCd
wirte ML2 09 ema N= 0 7:
if mCoy z= NCol:
Fe apparel ( Co J
Fe exppernet (C03)
N=zNTaL
AgmMesTy:
Veturm Fan
Fehr En
TO) fusion!
de§ key . fusion (ry:
nz rir)
FEnwL=a?
Telit L
ebse t
Me aci- see (LE: nr)
N= kei -fusiog |L[wi? D)
Pekmtn fusion (mM, J) 8 fore an Sees. itt
| Cok fas kek. = tops cle (=) wsdeTH? (uonpociant } R fetsece \V
Rappel & compléments al
Exercice 1:1 par sitton
1. Faire ioume Falgeritine de ti par sélection &
Pour I rie enone exsont
la insur ai
(8, 4,7,5,2,6,3)
2 Adapter ia fonetion iri selecion(7) pour trier wn tableau de nombres en ordre
croissant.
Exereige2 21
1
Inston
EEcrivez une fonction inserer(@L)_qui pend en argument une liste L supposte tie par
‘ordre croissant, et un nouvel ékiment e, et qui renvoie fa Hate abtenue en insérant
"element ela bonne place pour que le slat soit encore une list rig.
2 Eerivez ane fonction trier(L) qui end ae lite en argument et evoie la iste rig. On
uilisera Yeti par insertion: au début, on ene ane nouvelle liste vide, et ensuite, pour
‘aque élément ede la iste doigine, on nse dans a nouvelle liste
Exereice 31a hats
Principe: Evlgorthme parcowrt Te taleau, t compare Tes couples delements ween
Lorsqe devs éliments sucess me som pads ordre erosions ils sont Gehunges sprts
le premier parcours, le pl grand element xe retonne dans la derniee cate da teblcon, en
tab {Nel rete donc applique ta mésne procidure sur le table compote des clemente
‘tab{0) -. tabEN-2). Agrés chagve parcous complet dv tableny. Valgorione reconmneree
Vopévation, Loraqu'auewn éohange n'a ln penn in parcours, ela signiie que le ableae
‘strié. On arte alors Vaigorithne
Exemple Soi la lste Le
4,28)
Premiéreétape: on vada Ler élément i evant dernier
[5142.8] (15428) comme > ts
(1.542.8} [1432.8 meneroancar 4
(AS2.8}— 14.258) twenersamen 3-2.
142.58} [141235) Comme keene snips hang
Deusidme ape on va de Vavant dernir(L[-2)) ube
1,425.8) — (1.42.88) Méme principe q's Vetpe
[a2ss) 02.488)
8} 112458)
nent (en partan de a fn)
hme do fctuer erie purer
1 eta so vada Séme élément lft L3 ou Ter élément
8) = 11.2458)
(12458) (1.2488)
Comme ta list et tie, aucne inerverion wa How dete ape, equ prowoque Hardt de
olgoriine
crite une fonction ti_bulls(L) qui trie une liste £ selon la mSthode de or bulls. face TES AA
| Principe: Ler pur faion eat bast sur Ta inion dele les tries, De de dipart st
simple : on sépare te tubleau en dewe paties égales (ii un élément pris sf fe nombre
a élémers n'est pas pair), om wie ia premiére partic, on tre la densidme partie, puis on
fusionve ces deux povtiestriges, c'est.'caive qu'on prend le plus pet élément chr premier
sous tableau le plus pei élément da deus tableau tom place le plus pit des deus
dans le noweau tableau et ox recommence ainsi de suite. Bien entendu pour trier les deus
artes on fait de miéme, ce qui conduit dun nlgorithae récursf: Pour qu'il n'y at pas de
Probleme darré i supit de remarquer qu’ tableae damsel élément est nécessairement
Exenple :
TST Tesi une fonction fusion(L FL)
a ppenneliant de fasionner deve liste
Geko) ‘wies dans une nouvelle liste FUS et
2 a
a wt & Ys retourne le tésullat (On éeavtera la
solution consistant d eoncaténer les
88 ap ea B dee lstese1 wer le résulta)
wie une liste selon la msthode dei
per fusion,
[ Principe? La mathe cost & placer wv Wit de to (appl poll va place
dint, em permtont tons fs élment de elle sre que tous cen son iris au
Pivot sient ds gocher ue tous cu ui son spi avo sont droite
‘Le premier élément a du tblom et choi comme pivot; or réranne ens es ores,
‘ements de Tp placer to es élimens x avant a ets élments xa apr A
Je tabeon se compte maintenant en Isa; 12, o TE content miquemert des ements
infriurs met T2 miguenent des lémensspireus da. Eni, on apple réarivement
tu procedure pour trier Ter 2.
HERES coe
ates i wes
ay
4
1. Bxgeue algoitime sure oblean 105.3, 12,8, 17 » 45,419)
2. erire une fonction miRepidtL) qui rie we liste selon Ia née dt api
SpALy (4, AG ALG, 14%
Vous aimerez peut-être aussi
