1Metode desortare [604948]

1Metode desortare
-preg˘atire admitere –
Conf.dr. Alexandru Popa Lect. dr. Andrei P ˘atra¸ scu
Universitatea din Bucures ¸ti

2Cuprins
•Problema sort ˘arii
•Algoritmulde sortareprininterschimbare(Bubblesort)
•Algoritmulde sortareprininser¸ tie(Insertionsort)
•Algoritmulde sortareprinselec¸ tie(Selectionsort)
•Algoritmulde sortareprininterclasare(Mergesort)
•Algoritmulde sortarerapid ˘a(Quicksort)

3Problema sort ˘arii
•Fie un ¸ sirde“entit ˘a¸ ti”: e.g. numere,caractere,înregistr ˘arialeuneibazede date,
etc. Fiecareentitatede¸ tineo caracteristic ˘anumit˘acheiedesortare .
http://www.whydomath.org/Reading_Room_Material/ian_ stewart/shuffle/shuffle.html
•Exist˘a orela¸ tiedeordine ce se define¸ stepestemul¸ timeavalorilorposibileale
cheiidesortare.
•Sortarea ¸ sirului= dispunereaelementelor ¸ siruluiastfe lîncâtvalorilecheilorde
sortares˘ase afleîn ordinecresc ˘atoare(saudescresc ˘atoare)

4Problema sort ˘arii -Exemple
•Elementenumerice: [1,5,2,3,6,10,22,4,44]. În acestcazcheiade sortareeste
reprezentat ˘adeînsu¸ sielementul ¸ sirului.
•Elementedefinitedeînregistr ˘aricu maimultecâmpuri(nume ¸ si vârst ˘a):
(Andrei,29),(Paul,29),(Tiberiu,10),(Corina,25),(Cla udiu,19).
Dou˘a posibilecheidesortarepentrufiecareelement:
•Nume
•Vârst˘a
Sortaredup ˘anume:
(Andrei,29),(Claudiu,19),(Corina,25),(Paul,29),(Tib eriu,10).
Sortaredup ˘avârst˘a:
(Tiberiu,10),(Claudiu,19),(Corina,25),(Andrei,29),( Paul,29).

5Problema sort ˘arii
•Fie ¸ sirul:
x[1], x[2],···x[n].
Dac˘a not˘amcheiaelementului xicuKi, atuncisortarea ¸ siruluipresupune
determinareauneipermut ˘arip(1),p(2),···,p(n)astfelîncât:
Kp(1)≤Kp(2)≤···≤ Kp(n).
•Pentrusimplitate,consider ˘amc˘a cheiade sortare Kieste reprezentat ˘ade
întregulelement xi.

6Propriet˘a¸ ti ale metodelor de sortare
1.Eficien¸ ta . Oricemetod ˘ade sortareeste caracterizat ˘ade volumulderesurse
(timpde execu¸ tie)necesitatpentrurezolvareaproblemei .
•Num˘ardecompara¸ tii(de chei)
•Num˘ardedeplas ˘ari(de date)
2.Stabilitate . O metod ˘ade sortareeste stabil ˘adac˘aordinearelativ ˘aa elementelor
cu aceea¸ sicheiede sortarer ˘amâneneschimbat ˘a.
Aranjamentini¸ tial:
(Andrei,29),(Paul,29),(Tiberiu,10),(Corina,25),(Cla udiu,19).
Sortarestabil˘a:
(Tiberiu,10),(Claudiu,19),(Corina,25),(Andrei,29),( Paul,29).
Sortareinstabil˘a:
(Tiberiu,10),(Claudiu,19),(Corina,25),(Paul,29),(An drei,29).
3.Simplitate . O metod ˘ade sortareeste caracterizat ˘ade niveluldecomplexitateal
implement ˘ariisaleîn practic ˘a.

7Cuprins
•Problemasort ˘arii
•Algoritmul de sortareprin interschimbare(Bubble sort)
•Algoritmulde sortareprininser¸ tie(Insertionsort)
•Algoritmulde sortareprinselec¸ tie(Selectionsort)
•Algoritmulde sortareprininterclasare(Mergesort)
•Algoritmulde sortarerapid ˘a(Quicksort)

8Sortare prin interschimbare (Bubble sort)
Ideigenerale:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se parcurgesecven¸ tial ¸ sirul(elementcu element). Se com par˘aelementulcurent
cu urm˘atorul ¸ si,în cazulîn carese afl ˘aîn ordineanepotrivit ˘a,se interschimb ˘a.
•Seefectueaz ˘aparcurgeripân ˘a ¸ sirulnumai necesit ˘ainterschimb ˘ari

9Sortare prin interschimbare -Exemplu

10Sortare prin interschimbare
AlgoritmSort-Interschimbare (arrayx):
1.repeat
1.fori= 2···n
1.if(x[i]< x[i−1]) // dac ˘ax[i]¸ six[i−1]nusuntordonate
1.x[i−1]↔x[i]// seinterschimb ˘ax[i]cux[i−1]
2.swap=true
endif
endfor
until not swap // repet˘apân˘anumai suntnecesareinterschimb ˘ari
1.returnx

11Sortare prin interschimbare -Eficien¸ t ˘a
AlgoritmSort-Interschimbare (arrayx):
1.repeat
1.fori= 2···n
1.if(x[i]< x[i−1])
1.x[i−1]↔x[i]
2.swap=true
endif
endfor
until not swap
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:1 compara¸ tii
Pentrutoate valorile i:
n/summationdisplay
i=21 =n−1
Pentrutoate parcurgerile:
n−1≤TC(n)≤n(n−1)
2

12Sortare prin interschimbare -Eficien¸ t ˘a
AlgoritmSort-Interschimbare (arrayx):
1.repeat
1.fori= 2···n
1.if(x[i]< x[i−1])
1.x[i−1]↔x[i]
2.swap=true
endif
endfor
until not swap
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:Maxim2
Pentrutoate valorile i:
0≤Ti≤2(n−i)
Pentrutoate parcurgerile:
0≤TD(n)≤n(n−1)

13Sortare prin interschimbare -Eficien¸ t ˘a
•Compara¸ tii: n−1≤TC(n)≤n(n+1)
2
•Deplas˘arielemente: 0≤TD(n)≤n(n−1)
•Complexitatetotal ˘a:
n−1≤T(n) =TC(n)+TD(n)≤n(n+1)
2+n(n−1)≈O(n2)
•Cel maifavorabilcaz: 1,2,3,···,n;Cel mainefavorabil: n,n−1,···,1
•Algoritmuldesortareprininterschimbareeste stabil!
•Simpludeimplementat,darineficientpentru ¸ siruridedime nsiunimari!

14Cuprins
•Problemasort ˘arii
•Algoritmulde sortareprininterschimbare(Bubblesort)
•Algoritmul de sortareprin inser¸ tie(Insertionsort)
•Algoritmulde sortareprinselec¸ tie(Selectionsort)
•Algoritmulde sortareprininterclasare(Mergesort)
•Algoritmulde sortarerapid ˘a(Quicksort)

15Sortare prin inser¸ tie (Insertion sort)
Ideigenerale:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se parcurgesecven¸ tial ¸ sirul(elementcu element). Se ins ereaz˘aelementul
curent(x[i])în sub¸ sirulcareîl precede( x[1],x[2],···,x[i−1])astfel încât
acestas˘a r˘amân˘aordonat:
x[1],x[2],···,x[i−1],x[i],x[i+1],···,x[n]
•Sub¸ sirulce con¸ tineelementeledejasortatecre¸ stela fie careitera¸ tie,astfelîncât,
dup˘ace parcurgemtoate elementele,secven¸ taeste sortat ˘aîn întregime

16Sortare prin inser¸ tie -Exemplu
http://freefeast.info/general-it-articles/insertion -sort-pseudo-code-of-insertion-sort-insertion-sort- in-data-structure/

17Sortare prin inser¸ tie
AlgoritmSort-Inser¸ tie (arrayx):
1.fori= 2···n
1. aux←x[i] // fixareaelementului i
2.j←i−1
3.while(j >= 1)and (aux < x[j]) // c ˘autareapozi¸ tiei
1.x[j+1]←x[j] // deplasareelement x[j]pepozi¸ tia j+1
2.j←j−1
endwhile
4.x[j+1]←aux // deplasareelement x[i]pe pozi¸ tiac ˘autat˘a
endfor
2.returnx

18Sortare prin inser¸ tie -Eficien¸ t ˘a
Sort-Inser¸ tie (arrayx)
1.fori= 2···n
1.aux←x[i]
2.j←i−1
3.while(j >= 1)and(aux<x[j])
1.x[j+1]←x[j]
2.j←j−1
endwhile
4.x[j+1]←aux
endfor
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:
1≤Ti(n)≤i
Pentrutoate valorile i:
n−1≤TC(n)≤n(n+1)
2−1

19Sortare prin inser¸ tie -Eficien¸ t ˘a
Sort-Inser¸ tie (arrayx)
1.fori= 2···n
1.aux←x[i]
2.j←i−1
3.while(j >= 1)and(aux<x[j])
1.x[j+1]←x[j]
2.j←j−1
endwhile
4.x[j+1]←aux
endfor
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:
0+2≤Ti(n)≤(i−1)+2 = i+1
Pentrutoate valorile i:
2(n−1)≤TD(n)≤(n+1)(n+2)
2−3

20Sortare prin inser¸ tie -Eficien¸ t ˘a
•Compara¸ tii: n−1≤TC(n)≤n(n+1)
2−1
•Deplas˘arielemente: 2(n−1)≤TD(n)≤(n+1)(n+2)
2−3
•Complexitatetotal ˘a:
3(n−1)≤T(n) =TC(n)+TD(n)≤n2+2n−3≈O(n2)
•Cel maifavorabilcaz: 1,2,3,···,n;Cel mainefavorabil: n,n−1,···,1
•Algoritmuldesortareprininser¸ tieeste stabil!
•Este foartesimplude implementat(exist ˘aimplement ˘ariin5 liniide cod)!
•Recomandatpentru ¸ sirurirestrânsedeelemente(performa n¸ tepracticebune!)

21Sortare prin inser¸ tie binar ˘a
Ideigenerale:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se parcurgesecven¸ tial ¸ sirul(elementcu element). Se ins ereaz˘aelementul
curent(x[i])în sub¸ sirulcareîl precede( x[1],x[2],···,x[i−1]),folosind
algoritmulde c ˘autarebinar ˘a,astfelîncâtacestas ˘a r˘amân˘aordonat:
x[1],x[2],···,x[i−1],x[i],x[i+1],···,x[n]
•Îmbun˘at˘a¸ tirea metodeide sortareprininser¸ tiedirect ˘a: se înlocuie¸ steprocedura
de c˘autareliniar ˘a(O(n))cucea dec ˘autarebinar ˘a(O(log(n))).

22Sortare prin inser¸ tie binar ˘a
http://flylib.com/books/en/2.300.1.75/1/

23Sortare prin inser¸ tie binar ˘a
C˘autare-binar ˘a(arrayx, intp,intq, intkey):
1. mid= p + ((q-p)/2)2.if(key> x[mid])
1. return C˘autare-binar ˘a(x,mid+1,q,key)
else
1. return C˘autare-binar ˘a(x,p, mid,key)
endif
3.returnmid
•Complexitate: T(n) =O(log(n))
•Sortareaprininser¸ tiebinar ˘areducenum ˘aruldecompara¸ tiidela O(n2)laO(nlog(n))
•Cu toateastea,complexitateatotal ˘ase p˘astreaz˘aO(n2), datorit˘anum˘aruluide
deplas˘ari!

24Cuprins
•Problemasort ˘arii
•Algoritmulde sortareprininterschimbare(Bubblesort)
•Algoritmulde sortareprininser¸ tie(Insertionsort)
•Algoritmul de sortareprin selec¸ tie(Selectionsort)
•Algoritmulde sortareprininterclasare(Mergesort)
•Algoritmulde sortarerapid ˘a(Quicksort)

25Sortare prin selec¸ tie(Selection sort)
Ideigenerale:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se parcurgesecven¸ tial ¸ sirul(elementcu element). Se det ermin˘aminimum-uldin
sub¸ sirul( x[i],x[i+1],···,x[n]), ¸ sise înlocuie¸ stecu elementulcurent( x[i]).
[x[1],x[2],···,x[i−1],x[i],x[i+1],···,x[n]]
•Sub¸ sirulce con¸ tineelementeledejasortatesemare¸ stel a fiecareitera¸ tie,astfel
încât,dup ˘ace parcurgemtoate elementele,secven¸ taeste sortat ˘aîn întregime

26Sortare prin selec¸ tie-Exemplu
http://freefeast.info/general-it-articles/selection -sort-pseudo-code-of-selection-sort-selection-sort- in-data-structure/

27Sortare prin selec¸ tie
AlgoritmSort-Selec¸ tie (arrayx):
1.fori= 1···n−1
1.k←i
2.forj=i+1···n // c˘autareminimîn sub¸ sirul x[i:n]
1.ifx[k]> x[j]
1.k←j
endfor
3.ifk/n⌉gationslash=i// dac˘aelementulcurentnu esteminim-ulsub¸ sirului x[i:n]
1.x[k]↔x[i] // interschimbareminimcu elementulcurent
endfor
2.returnx

28Sortare prin selec¸ tie-Eficien¸ t ˘a
Sort-Selec¸ tie (arrayx):
1.fori= 1···n−1
1. k←i
2.forj=i+1···n
1.ifx[k]> x[j]
1.k←j
endfor
3.ifk/n⌉gationslash=i
1.x[k]↔x[i]
endfor
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:
Ti(n) =n−i
Pentrutoate valorile i:
TC(n) =n(n−1)
2

29Sortare prin selec¸ tie-Eficien¸ t ˘a
Sort-Selec¸ tie (arrayx):
1.fori= 1···n−1
1.k←i
2.forj=i+1···n
1.ifx[k]> x[j]
1.k←j
endfor
3.ifk/n⌉gationslash=i
1.x[k]↔x[i]
endfor
2.returnxOpera¸ tii:•
Compara¸ tii TC(n)
•Deplas˘arielemente TD(n)
Pentrufiecare i:
0≤Ti(n)≤3
•fiecare interschimbare nece-
sit˘a3 deplas ˘ari
Pentrutoate valorile i:
0≤TD(n)≤3(n−1)

30Algoritmul de sortare prin selec¸ tie-Eficien¸ t ˘a
•Compara¸ tii: TC(n) =n(n−1)
2
•Deplas˘arielemente: 0≤TD(n)≤3(n−1)
•Complexitatetotal ˘a:
n(n−1)
2≤T(n) =TC(n)+TD(n)≤n(n−1)
2+3(n−1)≈O(n2)
•Num˘arredusdedeplas ˘arielemente! (fa¸ t ˘ade Sortareaprininser¸ tie)
•Algoritmuldesortareprinselec¸ tie nuestestabil !

31Cuprins
•Problemasort ˘arii
•Algoritmulde sortareprininterschimbare(Bubblesort)
•Algoritmulde sortareprininser¸ tie(Insertionsort)
•Algoritmulde sortareprinselec¸ tie(Selectionsort)
•Algoritmul de sortareprin interclasare(Mergesort)
•Algoritmulde sortarerapid ˘a(Quicksort)

32Interclasare
•Fie ¸ sirurile: x[1],x[2],···,x[n]¸ siy[1],y[2],···,y[m](m≈n)ordonate
cresc˘ator;
•Procedurade interclasare
1. Se compar ˘aelementeleminimedinfiecare ¸ sir
2. Se returneaz ˘acel maimic
3. Se repet ˘apa¸ siipreceden¸ tipan ˘ala epuizareaelementelor
http://flylib.com/books/en/2.300.1.86/1/

33Interclasare
AlgoritmInterclasare (arrayx, arrayy)
1.i←1,j←1,k←1
2.whilej≤mandi≤n
2.ifxi≤yj
1.zk←xi
2.k←k+1
3.i←i+1
else
1.zk←yj
2.k←k+1
3.j←j+1
3.ifi > n
1.(zk,···,zm+n)←(xi,···,xn)
else
1.(zk,···,zm+n)←(yj,···,ym)
4. return z•ComplexitateO(m+n)
•Opera¸ tie mult mai simpl ˘a
decâtsortarea•Reducem procesul de sortare
laopera¸ tiideinterclasare: sein-terclaseaz ˘asub¸ siruridinceince
mai lungi, pân ˘a se ob¸ tine ¸ sirul
sortat.
<

34Sortare prin interclasare (Mergesort)
Structur˘ageneral ˘a:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se descompune ¸ sirulini¸ tialnesortatîn nsub¸ siruride lungime1
•Seinterclaseaz ˘asub¸ sirurileob¸ tinutelapasulprecedentpân ˘arezult˘aunsingur ¸ sir
http://interactivepython.org/courselib/static/pytho nds/SortSearch/TheMergeSort.html

35Sortare prin interclasare -Exemplu
https://en.wikipedia.org/wiki/Merge_sort#/media/Fil e:Merge_sort_algorithm_diagram.svg

36Algoritmul de sortare prin interclasare
AlgoritmSort-Interclasare (arrayx, intp, intq):
1.if(p < r)// wehaveatleast2items
1.q= (p+r)/2
2.Sort-Interclasare (x,p,q) // sortarex[p:q]
3.Sort-Interclasare (x,q+1,r) // sortarex[q+1:r]
4.Interclasare (x[p:q],x[q+1:r]) // interclasaresub¸ sirurilor
endif

37Sortare prin interclasare -Eficien¸ t ˘a
AlgoritmInterclasare (arrayx, arrayy)
1.i←1,j←1,k←1
2.whilej≤mandi≤n
2.ifxi≤yj
1.zk←xi
2.k←k+1
3.i←i+1
else
1.zk←yj
2.k←k+1
3.j←j+1
4.ifi > n
1.(zk,···,zm+n)←(xi,···,xn)
else
1.(zk,···,zm+n)←(yj,···,ym)•Opera¸ tiile dominante ale algorit-
muluiSort-Interclasare au loc in
proceduradeinterclasare•Se poate estima iterativ complexi-
tateaT(n):
•Problemaeste descompus ˘a
iterativindou ˘asubprobleme
cu dimensiuneredus ˘ala
jum˘atate
•Osubproblem ˘ade
dimensiune 1cost˘aO(1)
opera¸ tii
•Procedura de interclasarecost˘aO(n)

38Sortare prin interclasare -Eficien¸ t ˘a
•Complexitatetotal ˘a:O(nlog(n))
T(n) =1, dac˘an= 1
T/parenleftbig
⌈n
2⌉/parenrightbig
+T/parenleftbig
⌈n
2⌉/parenrightbig
+n,altfel.
•Recomandatpentru ¸ siruride maridimensiuni
•Cu toatec ˘a areo complexitatemaibun ˘a,în cazul ¸ sirurilordedimensiunemici,metoda
sort˘ariiprininser¸ tieprezint ˘aperforman¸ temaibunedecâtsortareaprininterclasare
•Algoritmuldesortareprininterclasare estestabil !

39Cuprins
•Problemasort ˘arii
•Algoritmulde sortareprininterschimbare(Bubblesort)
•Algoritmulde sortareprininser¸ tie(Insertionsort)
•Algoritmulde sortareprinselec¸ tie(Selectionsort)
•Algoritmulde sortareprininterclasare(Mergesort)
•Algoritmul de sortarerapid ˘a (Quicksort)

40Algoritmul de sortare rapid ˘a (Quicksort)
•AlgoritmdesortareeficientdezvoltatdeTonyHoareîn 1959 ¸ si publicatîn 1961
•Implement ˘arilebunepotdep ˘a¸ side2-3ori performan¸ telesort ˘ariiprininterclasare
Ideigenerale:
•Consider˘am ¸ sirul: x[1],x[2],···,x[n].
•Se alegedin ¸ sirunelement,numit pivot.
[x[1],x[2],···,x[i−1],x[i],x[i+1],···,x[n]]
Se realizeaz ˘aparti¸ tionarea ¸ sirului(în raportcu acestpivot): se reordoneaz ˘a ¸ sirul
astfelîncât elementelecu valorimaimici decâtpivotulseplaseaz ˘aînaintede
pivot,iarelementelecuvalorimaimari decâtpivotulse plaseaz ˘adup˘aacesta
(celeegaleîn oricaredinpar¸ ti).
•Dup˘a parti¸ tionare,pivotulseafl ˘a inpozi¸ tiafinal ˘a. Se aplic ˘arecursivaceea¸ si
procedur˘asub¸ siruluideelementecu valorimaimici,iarseparatsub ¸ siruluicu
valorimaimari.

41Algoritmul de sortare rapid ˘a (Quicksort)

42Algoritmul de sortare rapid ˘a (Quicksort)
AlgoritmQuicksort (arrayx, intl,inth)
1. if(l < h)
1. LocPivot= Partitionare (x,l,h)
2.Quicksort (x,l,LocPivot) //recursiepesegmentulelementelormaimici
3.Quicksort (x,LocPivot +1,h) // recursiesegmentelementemaimari
AlgoritmPartitionare (arrayx, intl,inth)
1. pivot= x[l]// consider ˘ampivotprimulelement
2. leftwall= l
3.fori=l+1···h
(a)if(x[i]<pivot)
1.x[i]↔x[leftwall] // elementul x[i]se mut˘aîn segmentulcorect
2. leftwall= leftwall +1
4. pivot↔x[leftwall]
5.returnleftwall

43Algoritmul de sortare rapid ˘a (Quicksort)
AlgoritmQuicksort (arrayx, intl,inth)
1. if(l < h)
1. LocPivot= Partitionare (x,l,h)
2.Quicksort (x,l,LocPivot)
3.Quicksort (x,LocPivot +1,h)
AlgoritmPartitionare (arrayx, intl,inth)
1. pivot= x[l]
2. leftwall= l
3.fori=l+1···h
(a)if(x[i]<pivot)
1.x[i]↔x[leftwall]
2. leftwall= leftwall +1
4. pivot↔x[leftwall]
5.returnleftwall•Opera¸ tiile dominante ale algo-
ritmuluiQuicksort aulocînpro-
ceduradeparti¸ tionare•Estimarecomplexitate T(n):
•Problemaestedescompus ˘aiterativin
dou˘asubproblemecu
dimensiuneredus ˘ala
jum˘atate
•Osubproblem ˘ade
dimensiune 1cost˘a
O(1)opera¸ tii
•Procedura de par-ti¸ tionarecost ˘a,încelmai
r˘aucaz,O(n)compara¸ tii

44Sortare prin interclasare -Eficien¸ t ˘a
•Complexitateîn cel mair ˘auscenariu:O(n2)
•Complexitateîn medie: O(nlog(n))
Avantaje:
•Necesit˘amemorieO(log(n)); multmairedus ˘adecâtsortareaprininterclasare
•Reprezint ˘aceamaibun ˘aalegerecândvitezaestefoarteimportant ˘a,indiferentde
dimensiuneasetuluide date.Dezavantaje :
•Poate ducelaumplereastiveicândse utilizeaz ˘aseturilargidedate.
•Performan¸ temodesteatuncicândopereaz ˘aasupraunorlisteaproapeordonate.
•Algoritmuldesortarerapid ˘a
este instabil !

45Concluzii
•O mul¸ timedemetodedesortarebazatepecompara¸ tiiîntre c hei,cu avantaje ¸ si
dezavantajeproprii
•Aplica¸ tiapractic ˘adicteaz˘aalegereametodei
•Metodeledesortareprininser¸ tie ¸ siselec¸ tieauperform an¸ tebunecând ¸ sirulde
sortatare dimensiunireduse
•Pentru ¸ siruride dimensiunimari: sortareprininterclasa re(Mergesort),sortare
rapid˘a(Quicksort),etc.