[SKAN MŪZIKA]
DAGS LOIDS: Tātad burbuļa kārtošana ir algoritms, ko varat izmantot
elementu kopas kārtošanai.
Apskatīsim, kā tas darbojas.
Tātad burbuļa kārtošanas pamatideja ir šāda.
Augstākās vērtības elementus mēs parasti vēlamies pārvietot pa labi,
zemākās vērtības elementus – pa kreisi, kas būtu sagaidāms.
Mēs vēlamies, lai zemākās lietas būtu sākumā, bet augstākās - beigās.
Kā mēs to darām?
Pseidokoda kodā, mēs varētu teikt, iestatīsim mijmaiņas skaitītāju uz
vērtību, kas nav nulle.
Pēc brīža mēs redzēsim, kāpēc mēs to darām.
Un tad mēs atkārtojam šo procesu, līdz mijmaiņas skaitītājs ir 0 vai
līdz mēs vispār neveicam mijmaiņas darbības.
Atiestatiet mijmaiņas skaitītāju uz 0, ja tas vēl nav 0.
Pēc tam apskatiet katru blakus esošo elementu pāri.
Ja šie divi elementi nav kārtībā, samainiet tos vietām un
pievienojiet 1 mijmaiņas skaitītājam.
Ja domājat par to, pirms to vizualizējat, ievērojiet, ka tas
pārvietos zemākās vērtības elementus pa kreisi un augstākās vērtības
elementus pa labi, efektīvi darot to, ko mēs vēlamies, proti,
pārvietot šīs elementu grupas šādā veidā.
Vizualizēsim, kā tas varētu izskatīties, izmantojot to masīvu, kurus
izmantojām, lai pārbaudītu šos algoritmus.
Šeit atkal ir nesakārtots masīvs, uz ko norāda visi elementi sarkanā
krāsā.
Un es iestatīju savu mijmaiņas skaitītāju uz vērtību, kas nav nulle.
Es patvaļīgi izvēlējos negatīvo 1 — tā nav 0.
Mēs vēlamies atkārtot šo procesu, līdz mijmaiņas skaitītājs ir 0.
Tāpēc es iestatīju mijmaiņas skaitītāju uz kādu vērtību, kas nav
nulle, jo pretējā gadījumā mijmaiņas skaitītājs būtu 0.
Mēs pat nesāktu algoritma procesu.
Tātad atkal ir šādas darbības: atiestatiet mijmaiņas skaitītāju uz 0,
pēc tam apskatiet katru blakus esošo pāri un, ja tie nav kārtībā,
samainiet tos vietām un pievienojiet mijmaiņas skaitītājam 1.
Tātad, sāksim šo procesu.
Tāpēc vispirms mēs iestatām mijmaiņas skaitītāju uz 0 un pēc tam
sākam aplūkot katru blakus esošo pāri.
Tā mēs vispirms sākam aplūkot 5 un 2.
Mēs redzam, ka tie nav kārtībā, tāpēc mēs tos samainām vietām.
Un mēs pievienojam 1 mijmaiņas skaitītājam.
Tātad tagad mūsu mijmaiņas skaitītājs ir 1, bet 2 un 5 ir pārslēgti.
Tagad mēs atkārtojam procesu vēlreiz.
Mēs skatāmies uz nākamo pāri blakus — 5 un 1 — tie arī nav kārtībā,
tāpēc mēs tos samainām vietām un pievienojam 1 mijmaiņas skaitītājam.
Tad mēs skatāmies uz 5 un 3.
Tie nav kārtībā, tāpēc mēs tos samainām vietām un pievienojam 1
maiņas skaitītājam.
Tad mēs skatāmies uz 5 un 6.
Tie ir kārtībā, tāpēc mums šoreiz nekas nav jāmaina.
Tad mēs skatāmies uz 6 un 4.
Tie arī nav kārtībā, tāpēc mēs tos samainām un pievienojam 1 maiņas
skaitītājam.
Tagad ievērojiet, kas ir noticis.
Mēs esam pārvietojuši 6 līdz beigām.
Tātad atlases kārtošanā, ja esat redzējuši to videoklipu, mēs
pārvietojām mazākos elementus, veidojot sakārtoto masīvu precīzi no
kreisās puses uz labo, no mazākā uz lielāko.
Burbuļa kārtošanas gadījumā, ja mēs sekojam šim konkrētajam
algoritmam, mēs faktiski veidojam sakārtoto masīvu no labās puses uz
kreiso, no lielākā uz mazāko.
Mēs esam faktiski uzburbulējuši 6, lielāko vērtību, līdz pat beigām.
Un tāpēc mēs tagad varam paziņot, ka tas ir sakārtots, un turpmākajās
iterācijās — vēlreiz izejot cauri masīvam — mums vairs nav jāņem
vērā 6.
Mums ir jāņem vērā tikai nesakārtoti elementi, kad skatāmies uz
blakus esošajiem pāriem.
Tātad mēs esam pabeiguši vienu piegājienu ar burbuļa kārtošanu.
Tagad mēs atgriežamies pie jautājuma - atkārtojiet, līdz mijmaiņas
skaitītājs ir 0.
Nu, mijmaiņas skaitītājs ir 4, tāpēc mēs turpināsim atkārtot šo
procesu vēlreiz.
Mēs atiestatīsim mijmaiņas skaitītāju uz 0 un apskatīsim katru blakus
esošo pāri.
Tāpēc mēs sākam ar 2 un 1 — tie nav kārtībā, tāpēc mēs tos samainām
vietām un pievienojam mijmaiņas skaitītājam 1.
2 un 3, tie ir kārtībā.
Mums nekas nav jādara.
3 un 5 ir kārtībā.
Mums tur nekas nav jādara.
5 un 4, tie nav kārtībā, tāpēc mums tie ir jāsamaina vietām un
jāpievieno 1 mijmaiņas skaitītājam.
Un tagad mēs esam pārvietojuši 5, nākamo lielāko elementu, uz
nesakārtotas daļas beigām.
Tātad tagad varam saukt šo sakārtotu daļu.
Tagad jūs skatāties uz ekrānu un, iespējams, tāpat kā es varu teikt,
sakāt, ka masīvs šobrīd ir sakārtots.
Bet mēs to vēl nevaram pierādīt.
Mums nav garantijas, ka tas ir sakārtots.
Un te spēlē ienāk mijmaiņas skaitītājs.
Tātad mēs esam pabeiguši piegājienu.
Mijmaiņas skaitītājs ir 2.
Tāpēc mēs atkārtosim šo procesu vēlreiz. Atkārtojiet, līdz mijmaiņas
skaitītājs ir 0.
Atiestatiet mijmaiņas skaitītāju uz 0.
Tā mēs to atiestatām.
Tagad apskatiet katru blakus esošo pāri.
Tas ir kārtībā, 1 un 2.
2 un 3 ir kārtībā.
3 un 4 ir kārtībā.
Tāpēc šajā brīdī ievērojiet, ka esam pabeiguši visu blakus esošo pāru
apskati, taču mijmaiņas skaitītājs joprojām ir 0.
Ja mums nav jāmaina nekādi elementi, tad saskaņā ar šo procesu tiem
ir jābūt kārtībā.
Un tad kārtošanas efektivitāte ir tas, kas mums, datorzinātniekiem,
tik patīk. Tas, ka tagad varam paziņot, ka viss masīvs ir sakārtots,
jo mums nebija jāmaina vietām elementi.
Tas ir diezgan jauki.
Tātad, kāds ir sliktākais scenārijs ar burbuļa kārtošanu?
Sliktākajā gadījumā masīvs ir pilnīgi apgrieztā secībā, un tāpēc mums
ir jāburbulē katrs lielais elements masīvā.
Un mums faktiski arī ir jāaizburbulē atpakaļ visi mazie elementi
masīvā.
Tātad katram no n elementiem ir jāpārvietojas pāri visiem pārējiem n
elementiem.
Tātad tas ir sliktākais scenārijs.
Savukārt, labākajā gadījumā tas nedaudz atšķiras no atlases
kārtošanas.
Masīvs jau ir sakārtots, kad mēs ieejam.
Mums nav jāveic nekādas mijmaiņas pirmajā piegājienā.
Tātad mums, iespējams, būs jāaplūko mazāk elementu, vai ne?
Mums šis process nav jāatkārto vairākas reizes.
Tātad, ko tas nozīmē?
Tad, kāds būtu sliktākais scenārijs burbuļa kārtošanai un kāds būtu
labākais burbuļa kārtošanas scenārijs?
Vai jūs to uzminējāt?
Sliktākajā gadījumā jums ir jāatkārto visi n elementi n reizes.
Tātad, sliktākais gadījums ir n kvadrātā.
Ja masīvs ir sakārtots nevainojami, katrs elements ir jāaplūko tikai
vienu reizi.
Un, ja mijmaiņas skaitītājs joprojām ir 0, varat teikt, ka šis masīvs
ir sakārtots.
Tātad labākajā gadījumā tas patiesībā ir labāks par atlases
kārtošanu — tas ir n omega.
Es esmu Dags Loids.
Šis ir CS50.