>> [MUSIC PLAYING]
>> DOUG LLOYD: OK, bel蓹 ki, bir birl蓹艧m蓹si sort ba艧qa bir alqoritm edir
biz h蓹yata d眉zm蓹k 眉莽眉n istifad蓹 ed蓹 bil蓹rsiniz ki, bir s谋ra elementl蓹ri.
Biz g枚r蓹c蓹ksiniz kimi, bu var ki, bir 莽ox fundamental f蓹rq
se莽im sort, bubble sort v蓹 durub s谋rala
ki, h蓹qiq蓹t蓹n, olduqca a臒谋ll谋 olun.
>> birl蓹艧m蓹si 蓹sas ideyas谋 sort ki莽ik seriallar谋n d眉zm蓹k 眉莽眉n
v蓹 h蓹min Diziler birl蓹艧dirm蓹k birlikd蓹 v蓹 ya Odur birl蓹艧m蓹si
s蓹b蓹bd蓹n s谋ralan谋r 眉莽眉n konseptual m蓹nada ad谋.
sort yoxdur birl蓹艧m蓹si yolu bu bir al蓹t istifad蓹 ed蓹r蓹k, var
n蓹 olan recursion adl谋 Biz tezlikl蓹 s枚hb蓹t etm蓹k olacaq
lakin biz, h蓹qiq蓹t蓹n h蓹l蓹 s枚hb蓹t yoxdur.
>> Burada birl蓹艧m蓹si s谋rala 蓹sas fikirdir.
Serial谋n sol yar谋m s谋rala n f蓹rz 1-d蓹n b枚y眉kd眉r.
M蓹n dey蓹nd蓹 n蓹 dem蓹k n f蓹rz 1 b枚y眉kd眉r
M蓹n biz raz谋 ed蓹 bil蓹r ki, bir s谋ra 蓹g蓹r yaln谋z bir element ibar蓹tdir,
s谋ralan谋r.
Biz, h蓹qiq蓹t蓹n, ehtiyac yoxdur bu bir 艧ey etm蓹k.
Biz yaln谋z s谋ralan谋r elan ed蓹 bil蓹r.
Bu, yaln谋z bir element var.
>> Bel蓹 pseudocode, t蓹krar edir serial谋n sol yar谋m sort
sonra sa臒 yar谋m array sort, sonra birlikd蓹 iki yar谋ya indirir daxil.
陌ndi art谋q ola bil蓹r d眉艧眉n眉r, bu c眉r yaln谋z
the-- Siz off qoyulmas谋 etdiyiniz kimi s蓹sl蓹nir Siz, h蓹qiq蓹t蓹n, he莽 bir 艧ey m蓹艧臒ul deyilik.
Siz sol sort dey蓹r蓹k edirik yar谋m, sa臒 yar谋m sort,
lakin izah deyilik M蓹n蓹 nec蓹 bunu edirik.
>> Amma uzun kimi xat谋rlay谋ram bir s谋ra bir element deyil,
biz s谋ralan谋r elan ed蓹 bil蓹r.
Sonra biz yaln谋z birlikd蓹 onlar谋 birl蓹艧dir蓹 bil蓹r.
V蓹 h蓹qiq蓹t蓹n Birl蓹艧m蓹 sort arxas谋nda 蓹sas ideyas谋,
ki, bunu q谋rmaq 眉莽眉n Sizin seriallarda 枚l莽眉s眉 biri var.
V蓹 sonra oradan b蓹rpa.
>> Sort m眉tl蓹q deyil Birle艧tirme m眉r蓹kk蓹b alqoritm.
V蓹 bu da bir az var g枚r眉nt眉l蓹m蓹k 眉莽眉n m眉r蓹kk蓹b.
Bel蓹likl蓹, 眉mid edir蓹m, vizual ki, m蓹n siz boyunca t蓹qib k枚m蓹k ed蓹c蓹k burada var.
M蓹n h蓹r 艧eyi r蓹vay蓹t m蓹nim 蓹n yax艧谋 莽al谋艧aca臒谋q v蓹 bu bir az daha vasit蓹sil蓹 davam
yava艧-yava艧 dig蓹r olanlar谋 daha yaln谋z in艧allah ba艧 almaq 眉莽眉n
Birl蓹艧m蓹 sort ideya 蓹traf谋nda.
>> Bel蓹likl蓹, biz eyni array var dig蓹r 莽e艧idl蓹nm蓹si alqoritm videos
Siz g枚rd眉m 蓹g蓹r Odur alt谋 element array.
V蓹 burada pseudocode kodu sortudur sol yar谋s谋, sa臒 yar谋m sort,
birlikd蓹 iki yar谋ya indirir daxil.
Bel蓹 ki, bu 莽ox qaranl谋q k蓹rpic q谋rm谋z谋 g枚t眉r蓹k array v蓹 bu sol yar谋m sort.
>> Haz谋rda Bel蓹 ki, biz gedirik sa臒 m蓹hsullar谋 ignore.
Bu var, lakin biz ist蓹yirik h蓹l蓹 ki, bir add谋m da.
Biz he莽 sort Serial谋n sa臒 yar谋m.
Biz n枚v sol ist蓹yirik serial谋n yar谋s谋.
V蓹 yaln谋z namin蓹 bir az daha olan
ayd谋n, m蓹n m眉raci蓹t ed蓹 bil蓹rsiniz n蓹 add谋m biz ist蓹yirik,
M蓹n ke莽id gedir蓹m nar谋nc谋 bu d蓹sti r蓹ng.
陌ndi, biz h蓹l蓹 s枚hb蓹t edirik orijinal s谋ra eyni sol yar谋s谋.
Amma ed蓹 ki, 眉mid edir蓹m m眉xt蓹lif madd蓹l蓹r r蓹ngl蓹ri bax谋n,
bu bir az daha etm蓹k laz谋md谋r burada neler t蓹mizl蓹m蓹k.
>> OK, bel蓹 ki, indi biz bir 眉莽 element array.
Bu sol yar谋m sort nec蓹 h蓹l蓹 bu add谋m array?
Biz sol d眉zm蓹k 眉莽眉n 莽al谋艧d谋臒谋n谋z k蓹rpic q谋rm谋z谋 serial谋n yar谋s谋
sol yar谋s谋 olan 陌ndi nar谋nc谋 r蓹ngli etdik.
>> Yax艧谋, biz c蓹hd v蓹 bil蓹r yen蓹 bu prosesi t蓹krar edin.
Bel蓹 ki, biz h蓹l蓹 d蓹 ist蓹yirik d眉zm蓹k 眉莽眉n 莽al谋艧谋r orta
tam array sol yar谋s谋.
sol yar谋s谋 array, m蓹n yaln谋z gedir蓹m
枚zba艧谋na q蓹rar ki, sol yar谋m sa臒 yar谋m daha ki莽ik olacaq,
bu olur, 莽眉nki 眉莽 elementd蓹n ibar蓹tdir.
>> V蓹 m蓹n ki, gedir蓹m sol yar谋m array sol yar谋s谋
yaln谋z element be艧 edir.
Be艧, bir element olan array, biz bu sort 眉莽眉n nec蓹.
V蓹 bel蓹 be艧 莽e艧idl蓹nir.
Biz yaln谋z b蓹yan olacaq.
Bu bir element array var.
>> Bel蓹likl蓹, biz indi s谋ralamas谋 etdik sol half-- sol yar谋s谋
daha do臒rusu, biz s谋ralan谋r etdik porta臒al sol yar谋s谋.
Bel蓹 ki, indi 眉莽眉n h蓹l蓹 tam 眉mumi serial谋n sol yar谋m,
biz sa臒 yar谋m d眉zm蓹k laz谋md谋r porta臒al, v蓹 ya bu m蓹hsullar谋.
Biz bunu nec蓹 ed蓹 bil蓹r蓹m?
B蓹li, biz iki element array var.
Bel蓹likl蓹, biz sol yar谋m sort bil蓹r iki serial谋n edir.
Iki bir elementidir.
Bel蓹 ki, ismar谋clar谋 s谋ralan谋r. Sonra biz sa臒 yar谋m s谋ralayabilirsiniz
array, bir hiss蓹sinin.
Bu default sort var.
>> Bu art谋q ilk d蓹f蓹 bir birl蓹艧m蓹si add谋m 蓹ld蓹 etdik.
Biz, baxmayaraq ki, ba艧a biz indi c眉r aldadan i莽 i莽蓹 edirik
ki, 莽蓹tin sort var recursion il蓹 艧ey,
Siz, Sizin saxlamaq laz谋md谋r Biz harada r蓹hb蓹rlik.
Bel蓹likl蓹, biz sol sort var nar谋nc谋 hiss蓹sinin yar谋s谋.
>> 陌ndi, biz 莽e艧idl蓹nm蓹si ortas谋nda ist蓹yirik nar谋nc谋 hiss蓹sinin sa臒 yar谋m.
V蓹 prosesi, biz add谋m olmaq indi,
birlikd蓹 iki yar谋ya indirir daxil.
Biz iki yar谋ya indirir baxd谋臒谋m谋zda serial谋n biz iki v蓹 bir bax谋n.
Hans谋 element ki莽ik?
Biri.
>> Sonra hans谋 element ki莽ik?
B蓹li, bu, iki v蓹 ya bir 艧ey var.
Bel蓹 ki, iki deyil.
Bel蓹 ki, indi yaln谋z yenid蓹n nizama salmaq 眉莽眉n Biz kontekstind蓹 oldu臒u,
biz bilmi艧ik porta臒al sol yar谋s谋
v蓹 m蓹n艧蓹 sa臒 yar谋m.
M蓹n r蓹ng d蓹yi艧di etdik bilirik biz harada yenid蓹n, lakin var.
V蓹 s蓹b蓹bi bu idi Bu proses, 莽眉nki
a艧a臒谋 iterating, davam etm蓹k niyy蓹tind蓹dir.
Biz sol s谋ralamas谋 etdik ke莽mi艧 porta臒al yar谋m
v蓹 ke莽mi艧 porta臒al sa臒 yar谋m.
>> 陌ndi biz bu daxil etm蓹k laz谋md谋r birlikd蓹 莽ox iki yar谋ya indirir.
Y蓹ni biz ist蓹yirik add谋md谋r.
Bel蓹likl蓹, biz b眉t眉n hesab 陌ndi ya艧谋l elementl蓹r,
Orijinal serial谋n sol yar谋m.
V蓹 biz bu birl蓹艧m蓹si eyni proses istifad蓹 ed蓹r蓹k,
biz iki birl蓹艧m蓹si 眉莽眉n etdi v蓹 bir yaln谋z bir an 蓹vv蓹l.
>> sol yar谋s谋, ki莽ik sol yar谋s谋nda element be艧 edir.
ki莽ik element haqq谋nda sa臒 yar谋m biridir.
O hans谋 ki莽ik?
Biri.
>> ki莽ik element haqq谋nda sol yar谋s谋 be艧 edir.
ki莽ik element haqq谋nda sa臒 yar谋m iki.
Ki莽ik n蓹dir?
Iki.
V蓹 sonra n蓹hay蓹t be艧 he莽 bir 艧ey, biz be艧 dem蓹k olar.
>> OK, bel蓹 ki, b枚y眉k 艧蓹kil, ed蓹k ikinci bir fasil蓹 etm蓹k
Biz harada v蓹 anlamaq.
Biz a莽谋lm谋艧 蓹g蓹r 蓹vv蓹ld蓹n, biz
陌ndi ba艧a 眉mumi array yaln谋z
burada pseudocode kodu bir add谋m.
Biz bilmi艧ik Serial谋n sol yar谋s谋.
>> Orijinal Xat谋rladaq ki, order be艧, iki, biri idi.
Bu prosesi il蓹 v蓹 a艧a臒谋 qu艧 balas谋 v蓹 t蓹krar,
problem q谋rmaq davam a艧a臒谋 ki莽ik v蓹 ki莽ik hiss蓹y蓹,
biz indi ba艧a pseudocode bir add谋m
b眉t眉n ba艧lan臒谋c array 眉莽眉n.
Biz sol yar谋m bilmi艧ik.
>> Bel蓹 ki, indi orada dondurmaq bildirin.
陌ndi h眉ququnu sort imkan Orijinal serial谋n yar谋s谋.
V蓹 biz bunu olacaq Eyni iterativ ke莽ir
艧eyi par莽alayaraq prosesi v蓹 sonra onlar谋 birlikd蓹 birl蓹艧m蓹si.
>> Bel蓹 ki, sol yar谋s谋 q谋rm谋z谋, v蓹 ya sol yar谋m
orijinal sa臒 yar谋s谋 array, m蓹n dem蓹k gedir蓹m 眉莽 edir.
Yen蓹 burada ard谋c谋l olan al谋ram.
Bir t蓹k varsa elementl蓹rin say谋, onu
h蓹qiq蓹t蓹n olub etm蓹z Siz sol, bir ki莽ik etm蓹k
v蓹 ya do臒ru bir ki莽ik.
>> Hans谋 m蓹s蓹l蓹 zaman siz蓹 ki, apar谋lmas谋 bu problem
bir birl蓹艧m蓹si, siz ard谋c谋l olmaq laz谋md谋r.
Siz ya h蓹mi艧蓹 laz谋md谋r sol yan ki莽ik etm蓹k
v蓹 ya h蓹mi艧蓹 etm蓹k laz谋md谋r sa臒 ki莽ik.
Burada h蓹mi艧蓹 se莽diyiniz sol t蓹r蓹find蓹 ki莽ik etm蓹k
zaman m蓹nim array, v蓹 ya m蓹nim sub-array, bir t蓹k 枚l莽眉s眉 edir.
>> 脺莽 bir element, v蓹 buna 莽e艧idl蓹nir.
Biz ehtimal谋 leveraged sonra Bizim b眉t眉n proses boyu bu g眉n蓹 q蓹d蓹r.
Bel蓹 ki, indi h眉ququ sort imkan sa臒 yar谋m yar谋s谋,
v蓹 ya q谋rm谋z谋 sa臒 yar谋m.
>> Yen蓹 bu a艧a臒谋 split laz谋md谋r.
Bu bir element array deyil.
Biz s谋ralan谋r elan ed蓹 bilm蓹z.
V蓹 bel蓹 ki, ilk, gedirik sol yar谋m sort.
>> sol yar谋s谋 bir element, bel蓹 ki, ismar谋clar谋 sort var.
Sonra sa臒 sort olacaq bir element yar谋m.
Bu ismar谋clar谋 s谋ralan谋r. V蓹 indi, Biz birlikd蓹 bu iki daxil ed蓹 bil蓹rsiniz.
D枚rd ki莽ik v蓹 sonra alt谋 ki莽ik.
>> Yen蓹 biz bu n枚qt蓹d蓹 etdik?
Biz sol s谋ralamas谋 etdik sa臒 yar谋s谋 yar谋s谋.
V蓹 ya orijinal geri gedir var idi r蓹ng,
biz sol s谋ralamas谋 etdik yum艧aq q谋rm谋z谋 yar谋s谋.
Bu, ilk qaranl谋q k蓹rpic idi q谋rm谋z谋 v蓹 indi daha yum艧aq q谋rm谋z谋,
v蓹 ya bir yum艧aq q谋rm谋z谋 idi.
>> V蓹 sonra biz s谋ralan谋r etdik yum艧aq q谋rm谋z谋 sa臒 yar谋m.
陌ndi d蓹, onlar yaln谋z yenid蓹n ya艧谋l ist蓹yirik Biz prosesi olacaq, 莽眉nki.
V蓹 biz t蓹krar var Bu 眉z蓹rind蓹.
>> Bel蓹 ki, indi biz bu daxil ed蓹 bil蓹rsiniz birlikd蓹 iki yar谋ya indirir.
V蓹 biz burada n蓹 var.
Qara x蓹tt Bel蓹 ki, yaln谋z sol yar谋m b枚l眉n眉r
v蓹 bu c眉r hiss蓹sinin sa臒 yar谋m.
>> Biz ki莽ik d蓹y蓹ri m眉qayis蓹 serial谋n sol t蓹r蓹find蓹
v蓹 ya pardon, ki莽ik yar谋da buraxd谋 d蓹y蓹ri
h眉ququnun ki莽ik d蓹y蓹ri yar谋m v蓹 眉莽 ki莽ik oldu臒unu tapmaq.
陌ndi bir optimalla艧d谋r谋lmas谋 bir az, sa臒?
He莽 bir 艧ey h蓹qiq蓹t蓹n var sol t蓹r蓹find蓹 ayr谋ld谋.
>> Qalan bir 艧ey yoxdur sol t蓹r蓹find蓹,
bel蓹 ki, biz s蓹m蓹r蓹li ed蓹 bil蓹rsiniz yaln谋z biz elan ed蓹 bil蓹r move--
Bunun qalan 蓹slind蓹 莽e艧idl蓹nir v蓹 yaln谋z tack
he莽 bir 艧ey yoxdur, 莽眉nki, qar艧谋 m眉qayis蓹 眉莽眉n ba艧qa.
V蓹 biz bilirik sa臒 ki, Sa臒 莽e艧idl蓹nir.
>> OK, bel蓹 ki, indi yenid蓹n dondurmaq imkan v蓹 Biz hekay蓹 harada 艧ekillendirmek.
脺mumi array, biz n蓹 h蓹yata var?
Biz, h蓹qiq蓹t蓹n, yerin蓹 yetirm蓹k etdik indi bir add谋m iki add谋mlar.
Biz sol yar谋m s谋ralan谋r, v蓹 biz sa臒 yar谋m s谋ralan谋r.
>> Bel蓹 ki, indi qal谋r ki, b眉t眉n bizim 眉莽眉n birlikd蓹 bu iki yar谋ya indirir daxil etm蓹k 眉莽眉n.
Bel蓹likl蓹, biz 蓹n a艧a臒谋 qiym蓹tli m眉qayis蓹 serial谋n h蓹r yar谋m element
v蓹 枚z n枚vb蓹sind蓹 davam etdirilir.
脺莽 azd谋r, bel蓹 ki, bir gedir.
>> 陌ki 眉莽 azd谋r, bel蓹 ki, iki gedir.
脺莽 5-d蓹n az, bel蓹 ki, 眉莽 gedir.
D枚rd 5-d蓹n az, bel蓹 ki, d枚rd gedir.
Sonra be艧, alt谋 azd谋r v蓹 alt谋 b眉t眉n qal谋r.
>> 陌ndi m蓹n bilir蓹m ki, add谋mlar bir 莽ox idi.
V蓹 biz bir 莽ox t蓹rk etdik Bizim sonra yadda艧.
V蓹 o boz meydanlar谋n n蓹 var.
Ki, etdi kimi v蓹 y蓹qin ki, hiss durub s谋rala art谋q 莽ox, bubble
sort, v蓹 ya se莽im sort.
>> Amma 蓹slind蓹, 莽眉nki Bu prosesl蓹rin 莽ox
Eyni s媒rada da olur ki, yen蓹 biz laz谋md谋r bir 艧ey deyil
Biz haqq谋nda dan谋艧maq zaman haqq谋nda dan谋艧maq g蓹l蓹c蓹kd蓹 recursion video--
h蓹qiq蓹t蓹n bu alqoritm ayd谋n 蓹sasl谋 deyil
bir 艧ey daha f蓹rqli biz 蓹vv蓹l g枚rd眉k
lakin 蓹h蓹miyy蓹tli d蓹r蓹c蓹d蓹 d蓹 daha s蓹m蓹r蓹li.
>> Niy蓹 ki?
Yax艧谋, pis ssenari, biz
n elementl蓹ri split v蓹 sonra onlar谋 recombine.
Amma biz recombine zaman Onlara n蓹 edirik
蓹sas蓹n iki qat谋na 莽谋xar谋r ki莽ik seriallarda 枚l莽眉s眉.
Biz bir element bir d蓹st蓹 var Diziler ki, biz s蓹m蓹r蓹li
iki element seriallar谋n daxil birl蓹艧dirir.
V蓹 sonra biz bu almaq iki element Diziler
v蓹 onlar谋 birlikd蓹 birl蓹艧dirm蓹k bel蓹 d枚rd element Diziler, v蓹,
v蓹 s, v蓹 s, biz q蓹d蓹r bir n element array var.
>> Amma nec蓹 bir 莽ox doublings Bu n almaq laz谋md谋r?
Geri telefon kitab misal d眉艧眉n眉n.
Ne莽蓹 d蓹f蓹 biz qoparmaq var yar谋s谋nda telefon kitab, nec蓹 daha 莽ox
d蓹f蓹 biz telefon kitab qoparmaq var yar谋s谋nda, 蓹g蓹r telefon kitab 枚l莽眉s眉
iki d蓹f蓹?
Yaln谋z bir do臒ru var?
>> Bel蓹 ki, bir n枚v var burada logarithmic element.
Amma biz d蓹 h蓹l蓹 蓹n az谋 n elementl蓹ri b眉t眉n baxmaq.
, 茝n pis halda bel蓹 sort n log n 莽al谋艧谋r birl蓹艧m蓹si.
Biz baxmaq laz谋md谋r n elementl蓹ri b眉t眉n,
v蓹 biz onlar谋 birl蓹艧dirm蓹k laz谋md谋r birlikd蓹 log n add谋mlar d蓹stl蓹ri.
茝n yax艧谋 ssenari, array m眉k蓹mm蓹l 莽e艧idl蓹nir.
Bu 蓹lad谋r.
Amma alqoritm 蓹sas谋nda biz burada var biz h蓹l蓹 split v蓹 recombine laz谋md谋r.
Bu halda olsa da, recombining t蓹sirsiz n枚v眉d眉r.
Bu laz谋m deyil.
Amma biz h蓹l蓹 ke莽m蓹k h蓹r halda b眉t眉n proses.
>> 茝n yax艧谋 halda bel蓹 v蓹 蓹n pis halda,
bu alqoritm n log n vaxt 莽al谋艧谋r.
Sort Birle艧tirme m眉tl蓹q bir az trickier edir dig蓹r 蓹sas 莽e艧idl蓹nm蓹si alqoritml蓹rin 莽ox
biz CS50 haqq谋nda s枚hb蓹t ancaq etdik 蓹h蓹miyy蓹tli d蓹r蓹c蓹d蓹 daha g眉cl眉.
>> V蓹 蓹g蓹r he莽 tapmaq m眉nasib蓹til蓹 onu laz谋md谋r
v蓹 ya d眉zm蓹k 眉莽眉n istifad蓹 etm蓹k b枚y眉k data set 蓹ld蓹
recursion ideyas谋 蓹traf谋nda ba艧 h蓹qiq蓹t蓹n g眉cl眉 olacaq.
V蓹 bu etm蓹k olacaq sizin proqramlar谋 h蓹qiq蓹t蓹n daha s蓹m蓹r蓹li
ba艧qa bir 艧ey qar艧谋 sort daxil istifad蓹 ed蓹r蓹k.
M蓹n Doug Lloyd edir蓹m.
Bu CS50 edir.