[SKAN MŪZIKA]
DAGS LOIDS: Labi, līdz šim esam runājuši par dažiem kārtošanas
algoritmiem, ar kuriem, cerams, ir diezgan vienkārši strādāt.
Mums ir burbuļa kārtošana, ievietošanas kārtošana un atlases
kārtošana.
Un mēs zinām, ka tām ir sava veida sliktākā scenārija izpildlaiks n
kvadrātā.
Vai mēs varam to uzlabot?
Nu, atbilde ir jā, mēs varam, izmantojot algoritmu, ko sauc par
sapludināšanas kārtošanu.
Sapludināšanas kārtošanas ideja ir – sakārtot mazākus masīvus un pēc
tam apvienot šos masīvus vai apvienot tos sakārtotā secībā, kā
norādīts paša algoritma nosaukumā.
Tā vietā, lai domātu, mums ir viens sešu elementu masīvs, domāsim, ka
mums ir seši viena elementa masīvi, un tad vienkārši apvienosim tos
pareizā secībā un sapludināsim kopā.
Tas būtu viens no veidiem, kā to sakārtot.
Un to dara sapludināšanas kārtošana.
Un tā izmanto kaut ko, ko sauc par rekursiju, par ko mēs drīz runāsim
citā videoklipā.
Un, ja vēlaties iegūt labāku izpratni par to, kā darbojas rekursija,
iespējams, vēlēsieties apskatīt to videoklipu, pirms skatīsieties šo,
jo te diezgan daudz runāsim par rekursiju.
Sapludināšanas kārtošana noteikti ir vissarežģītākā no visiem četriem
kārtošanas veidiem, kurus mēs aplūkojam šajā kursā.
Un tāpēc es iešu cauri šim nedaudz lēnāk nekā pārējiem.
Bet pašam sapludināšanas kārtošanas algoritmam patiesībā ir diezgan
maz soļu.
Būtībā mēs teiksim: mēs kārtosim masīva kreiso pusi, kārtosim masīva
labo pusi, un pēc tam sapludināsim abas puses.
Tas būtībā ir sapludināšanas veids.
Protams, praksē tas ir daudz detalizētāks, bet tagad aplūkosim šo.
Tātad, šeit ir tas pats sešu elementu masīvs, kuru mēs visu laiku
esam kārtojuši.
Un mēs sāksim sekot mūsu pseidokoda soļiem, proti, mēs vēlamies
sakārtot šī ķieģeļsarkanā masīva kreiso pusi.
Tāpēc mēs pagaidām koncentrēsimies tikai uz šo daļu.
Un patiesībā, lai lietas būtu nedaudz vienkāršākas, un tāpēc, ka šajā
videoklipā esmu krāsojis dažādas lietas dažādos veidos, sākot ar šo
momentu, mēs sauksim šo kopējā sarkanā masīva kreiso pusi par
purpursarkano masīva pusi.
Labi?
Tātad mēs šobrīd esam masīva kreisās puses kārtošanas procesā.
Bet mēs nezinām, kā to izdarīt.
Mēs nezinām, kā sakārtot masīva kreiso pusi.
Tātad, kāpēc mēs vienkārši neatgriežamies pie sapludināšanas
kārtošanas darbībām?
Labi, ja es nezinu, kā kārtot masīva kreiso pusi, es vienkārši sākšu
no jauna.
Kārtojiet šī masīva kreiso pusi.
Tagad es vēlos koncentrēties tikai uz šo masīva daļu, kreiso pusi.
Un es kaut kā patvaļīgi nolemju, ka mana kreisā puse būs mazāka par
labo pusi.
Man ir trīs elementi.
Es nevaru tos sadalīt vienmērīgi.
Man nevar būt viens un 1/2 elementi katrā pusē.
Tātad, kamēr es esmu konsekvents, kamēr es vienmēr izvēlos, šajā
gadījumā kreisā puse ir mazāka, tas derēs sapludināšanas kārtošanas
nolūkiem.
Tāpēc tagad man ir palicis šis vienīgais elements, šis elements pieci.
Kā kārtot viena elementa masīvu?
Labas ziņas šeit ir tādas, ka man tas nemaz nav jākārto.
Viena elementa masīvs obligāti ir jāsakārto.
Tāpēc es varu teikt, ka, ja es kārtoju purpursarkanās daļas kreiso
pusi, tā ir sakārtota.
Mēs to vienkārši nosauksim to par sakārtotu un pagaidām atliksim malā.
Tāpēc tagad es vēlos atgriezties pie purpursarkanās daļas labajā pusē.
Tā ir šī.
Kā kārtot šo masīvu, šo apakšmasīvu?
Atgriezīsimies atpakaļ pie saviem soļiem.
Es gribu kārtot tikai kreiso pusi.
Kreisajā pusē tagad ir divi.
Tas ir viens elements.
Es zinu, kā kārtot vienu elementu.
Tāpēc es esmu sakārtojis šo kreiso pusi, purpursarkanās daļas labās
puses kreiso pusi.
Re, kur mēs esam.
Tas ir sakārtots.
Tagad es atgriežos un kārtoju purpursarkanās kreisās puses labo pusi,
kas ir viens.
Viens ir viens elements.
To ir patiešām viegli sakārtot.
Tas ir sakārtotā pozīcijā.
Tagad ir pirmā reize, kad beidzot tieku pie šīs sapludināšanas
kārtošanas trešā posma, kurā es sapludinu abas puses kopā.
Tātad, šeit man ir jāņem vērā šīs divas gaiši zaļās pusītes.
Un man ir jāizlemj, kurai ir zemāks elements.
Šajā gadījumā tas ir viens.
Tāpēc es paņemu vienu un ievietoju to kāda jaunā hipotētiskā masīva
pirmajā pozīcijā.
Tad es salīdzinu abus ar neko un jautāju, kurš no tiem ir zemāks.
Nu, divi vai nekas.
Kas ir zemāks, tas ir divi.
Tātad tagad pārkadrēsim attēlu, jo, ja atceramies rekursiju, mēs
koncentrējāmies tikai uz kieģeļsarkanā masīva kreiso pusi, ko tad
saucām par purpursarkano masīvu.
Šajā posmā esam sakārtojuši purpursarkanā masīva kreiso pusi, kas ir
pieci, un labo pusi, kas sākotnēji bija divi un viens, bet tagad esam
veikuši šīs sapludināšanas darbības un esam to izdarījuši pareizā
secībā.
Tātad tagad esam trešajā darbības posmā, jo mēs jau esam sakārtojuši
purpursarkanā masīva kreiso pusi un purpursarkanā masīva labo pusi.
Tāpēc tagad mums ir jāsapludina šīs divas puses.
Un tāpat kā darījām pirms brīža ar divi un viens, mēs salīdzināsim
kreisās daļas pirmo elementu un labās daļas pirmo elementu,
noskaidrosim, kurš no tiem ir mazāks, un padarīsim to par mūsu jauna
masīva pirmo elementu.
Tāpēc es salīdzinu pieci un viens.
Un es saku, kurš ir mazāks?
Nu, tas ir viens, tāpēc viens kļūst par pirmo šī jaunā trīs elementu
masīva elementu.
Tagad man jāpieņem cits lēmums.
Pieci ir zemāks vai divi ir zemāks?
Nu divi ir zemāks.
Tātad divi kļūst par nākamo mūsu sapludināšanas soļa elementu.
Tad es saku, vai pieci ir zemāks vai nekas ir zemāks?
Skaidrs, ka šajā gadījumā vienīgais variants, kas man paliek ir pieci.
Un tāpēc tagad, šajā momentā, atkal rekursīvi domāsim par to, kur mēs
atrodamies.
Mēs esam sakārtojuši visu sarkano masīvu, esam veikuši tikai pirmo
darbību.
Mēs esam sakārtojuši kreiso daļu.
Mēs to darījām rekursīvi, bet esam sakārtojuši kopējā sarkanā masīva
kreiso daļu.
Līdz ar to mēs varam to pagaidām atstāt malā, jo tagad mums ir
jādodas uz sapludināšanas kārtošanas procesa nākamo soli, proti,
jākārto sarkanā masīva labā puse.
Tātad pāriesim un koncentrēsimies uz labo pusi.
Mēs veiksim tieši tās pašas darbības, kuras tikko veicām ar kreiso
daļu.
Bet tagad mēs to darīsim ar šo sarkano daļu labajā pusē.
Tāpēc es vēlos sakārtot šī masīva kreiso pusi.
Nu, tas ir diezgan vienkārši.
Es vienkārši patvaļīgi atkal to sadalu.
Es skatos uz to.
Es saku: labi, trīs ir viens elements.
Viens elements jau ir sakārtots, tāpēc man nekas nav jādara, kas ir
lieliski.
Es varu vienkārši atstāt to malā un teikt, ka trīs jau ir sakārtots.
Tagad es gribu sakārtot labo pusi no ne tik ķieģeļsarkanās, bet
joprojām sarkanās masīva puses, kas ir šī daļa.
Kā to izdarīt?
Nu, tas ir vairāk nekā viens elements.
Tāpēc es atkal atgriezīšos pie sava procesa sākuma.
Es kārtošu šī masīva kreiso pusi.
Tad es paskatos un saku, lūk, kreisā puse.
Tas ir seši.
Tas jau ir sakārtots.
Tagad es kārtošu masīva labo pusi.
Tas ir četri.
Tas jau ir sakārtots.
Tagad es atkal nonāku pie sapludināšanas posma, kur man atkal ir
jāveic šāda veida salīdzinājumi.
Kurš ir zemāks?
Seši ir zemāks vai četri ir zemāks?
Nu, četri ir zemāks, tāpēc tas kļūst par mūsu jaunā sapludināta mazā
apakšmasīva pirmo elementu.
Un tad man ir jāizvēlas starp seši un neko.
Un es saku, seši ir mazākais atlikušais.
Tāpēc tagad esmu sakārtojis labās puses kreiso pusi.
Un es esmu sakārtojis labās puses labo pusi.
Tāpēc tagad es vēlos sapludināt šīs divas daļas.
Un atkal mēs veiksim tieši to pašu procesu, ko veicām ar kreiso daļu.
Es teikšu, trīs ir zemāks vai četri?
Nu, tas ir trīs.
Un tad es teikšu, četri ir zemāks, vai nekas?
Kreisajā pusē nekas nav palicis, tad man jāzina, ka visam labajā pusē
ir jābūt lielākam par visu, kas šobrīd ir sapludinātajā masīvā.
Tāpēc tā vietā, lai teiktu: Labi, es ielikšu četri un tad seši, jo
tikai tie ir palikuši vienā pusē, visam ir jāiet.
Tātad viss nokrīt.
Un atkal padomāsim par to, kur esam.
Šajā brīdī sākotnējam ķieģeļsarkanajam masīvam, ar kuru mēs sākām,
esam veikuši divas mūsu pseidokoda darbības.
Mēs esam sakārtojuši kopējā ķieģeļsarkanā masīva kreiso pusi.
Un mēs esam sakārtojuši šī kopējā ķieģeļsarkanā masīva labo pusi.
Un tagad pēdējais, kas mums jādara, ir sapludināt šīs divas puses.
Un tāpat kā iepriekš, mēs atkal turpinām uzdot sev to pašu jautājumu.
Kas ir zemāks, viens vai trīs?
Ievērojiet mazo melno līniju, kas sadala abas puses, lai padarītu to
vizuāli skaidrāku.
Kas ir zemāks, viens vai trīs?
Nu, viens.
Tagad atkal uzdodu sev jautājumu, kas ir zemāks, divi vai trīs?
Tas būtu divi.
Kas ir zemāks, pieci vai trīs?
Tas ir trīs.
Pieci vai četri?
Tas ir četri.
Pieci vai seši.
Tas ir pieci.
Seši vai nekas?
Tas ir seši.
Un tāpēc, veicot šo procesu rekursīvi un sadalot savu problēmu
mazākos un mazākos apakšmasīvos, kārtojot tos, sapludinot tos kopā,
pēc vairākām darbībām esmu pabeidzis savu kārtošanu.
Un man te viss ir sakārtots tumši zilā krāsā.
Viens, divi, trīs, četri, pieci, seši.
Tas ne vienmēr ir tik vienkārši kā burbuļa kārtošana, ievietošanas
kārtošana vai atlases kārtošana.
Bet vai šeit ir kādas priekšrocības?
Nu, atbilde ir - jā, ir.
Sliktākajā gadījumā mums ir jāsadala n elementi.
Un tad mums tie ir jāpārkombinē, efektīvi dubultojot sakārtotos
masīvus, veidojot tos.
Tātad mēs ņemam divus viena elementa masīvus un pārvēršam tos par
divu elementu masīvu.
Mēs ņemam divus divu elementu masīvus.
Mēs pārveidojam tos četru elementu masīvā.
Un tā tālāk, un tā tālāk, un tā tālāk.
Labākajā gadījumā, piemēram, atlases kārtošana, masīvs jau ir
sakārtots, bet mēs to nezinām.
Mēs to nezinām, kamēr mēs to nesadalām un atkal apvienojam ar šo
algoritmu.
Šeit nav nekāda veida saīsnes, izņemot iepriekšēju meklēšanu.
Bet tas arī papildinās papildu laiku.
Tātad rezultāts ir tāds, ka mums ir n elementi — un, iespējams, mums
tie ir jāapvieno, ja mēs dubultojam — log n reizes.
Matemātiski tas darbojas šādi.
Tātad patiesībā, atšķirībā no citiem apskatītajiem algoritmiem,
sliktākajā gadījumā sapludināšanas kārtošanas izpildes laiks ir O no
n log n, kas kopumā būs mazāks vai ātrāks par n kvadrātā.
Labākajā gadījumā tas joprojām ir n log n, jo mums vēl ir jāiziet šis
process vēlreiz.
Tātad labākajā gadījumā tas var būt lēnāks nekā, piemēram, burbuļa
kārtošana, kur masīvs ir lieliski sakārtots.
Kā jūs atceraties omega, tur ir n, nevis n log n.
Bet sliktākajā gadījumā vai varbūt pat ierastajā gadījumā
sapludināšanas kārtošana faktiski būs ātrāka, iespējams, aizņemot
vairāk atmiņas, jo mums ir jāpārkombinē un jāveido mūsu apakšmasīviem
jauni segmenti atmiņā.
Tātad sapludināšanas kārtošana ir patiešām jaudīgs rīks, kas
jāiekļauj jūsu rīklodziņā, tiklīdz jūs saprotat rekursiju, jo tas var
paātrināt masīva kārtošanas procesu.
Mani sauc Dags Loids.
Šis ir CS50.