>> [Mūzikas atskaņošanai]
Doug LLOYD: Labi, tāpēc burbulis šķirot ir algoritms
Jūs varat izmantot, lai sakārtotu elementu kopumu.
Pieņemsim to apskatīt, kā tā darbojas.
>> Tātad Pamatideja burbulis šķirot tas ir.
Mēs parasti gribam virzīties augstāka vērtē elementi parasti pa labi,
un nolaidiet vērtē elementus parasti pa kreisi, kā mēs varētu gaidīt.
Mēs vēlamies, zemākas lietas būt sākums, un augstākās lietas
būt beigās.
>> Kā mēs to darām?
Nu pseudocode kodu, mēs varētu teikt, pieņemsim
noteikt aizstāšanas counter kas nav saistīts ar nulles vērtību.
Mēs redzēsim, kāpēc mēs to darām, ka sekundē.
Un tad mēs atkārtot šādu process, līdz mijmaiņas skaitītājs ir 0,
vai līdz brīdim, kad mēs nepieļaujam mijmaiņas darījumus vispār.
>> Reset mijmaiņas counter līdz 0, ja tas nav jau 0.
Tad apskatīt katru blakus pāri no elementiem.
Ja šie divi elementi ir nav kārtībā, mijmaiņas tiem,
un pievienot 1 līdz swap letes.
Ja jūs domājat par tas pirms jūs vizualizēt to,
ievērosiet, ka tas pāries zemāks vērtē elementi kreisi
un augstāka vērtē elementus tiesībām, efektīvi darīt to, ko mēs vēlamies darīt,
kas ir pārvietot šos grupas Elementu šādā veidā.
Pieņemsim iztēloties, kā tas varētu izskatīties, izmantojot mūsu masīvs
ka mēs izmantojām, lai pārbaudītu out šiem algoritmiem.
Mums ir nešķirotas masīvs šeit atkal, norādīts ar visiem elementiem
ir sarkanā krāsā.
Un es noteikt manu mijmaiņas skaitītājs līdz nulle vērtības.
Es patvaļīgi izvēlējās negatīvs 1-- tas nav 0.
Mēs vēlamies, lai atkārtot šo procesu līdz mijmaiņas letes ir 0.
Tas ir iemesls, kāpēc es noteikt manu swap pretrunā ar kādu ne-nulles vērtību,
jo pretējā gadījumā swap skaitītājs būtu 0.
Mēs nebūtu pat sākas process algoritms.
Tātad vēlreiz, soļi are-- reset mijmaiņas skaitītāju
0, tad apskatīt katru blakus pāris, un, ja viņi no rīkojuma,
mijmaiņas tiem, un pievieno 1 uz swap letes.
Tātad, pieņemsim sākt šo procesu.
Tātad, pirmā lieta, kas mums jādara, ir mēs noteikti mijmaiņas skaitītāju uz 0,
un tad mēs sākt meklēt katrā divām blakus esošajām.
>> Tātad mēs vispirms sākt meklēt pie 5 un 2.
Mēs redzam, ka tie ir no pasūtīt un tāpēc mēs mijmaiņas tiem.
Un mēs pievienojam 1 līdz swap letes.
Tātad tagad mūsu swap skaitītājs ir 1, un 2 un 5 ir ieslēgta.
Tagad mēs atkal atkārtojiet procesu.
>> Mēs apskatīt nākamajā divām blakus esošajām, 5 un 1-- viņi arī no rīkojuma,
tāpēc mēs mijmaiņas tiem un pievienot 1 uz mijmaiņas letes.
Tad mēs skatāmies 5 un 3.
Tie ir iziet no ierindas, tāpēc mēs mijmaiņas viņiem un mēs pievienot 1 līdz swap letes.
Tad mēs skatāmies uz 5 un 6.
Viņi lai, tāpēc mums nav reāli nepieciešams apmainīt Jebkas šoreiz.
Tad mēs skatāmies uz 6 un 4.
Viņi arī iziet no ierindas, tāpēc mēs mijmaiņas viņiem un mēs pievienot 1 līdz swap letes.
>> Tagad pamanīt to, kas ir noticis.
Mēs esam pārvietots 6 visu ceļu līdz beigām.
Tātad atlases veida, ja jūs esat redzams, ka video, ko mēs darījām, bija
mēs beidzās pārvietojot mazākie elementi ēkā
šķiroto masīvs būtībā no kreisās puses uz labo, mazākais uz lielāko.
Attiecībā uz burbuļa veida, ja mēs pēc šo konkrēto algoritmu,
mēs tiešām gribam būt ēkas šķiroto masīvs no labās
pa kreisi, vislielākā uz vismazāko.
Mums ir efektīvi burbuļojot 6, to lielākā vērtība, visu ceļu līdz beigām.
>> Un tāpēc mēs tagad varam paziņot, ka tas ir sakārtots,
un nākotnē iterations-- iet cauri masīva again--
mums nav jāapsver 6 vairs.
Mums tikai ir jāapsver nešķirotajiem elementi
kad mēs esam apskatot blakus esošiem pāriem.
Tātad mēs esam pabeiguši vienu iet cauri burbuļu veida.
Tāpēc tagad mēs ejam atpakaļ uz jautājumu, atkārto, līdz mijmaiņas skaitītājs ir 0.
Nu mijmaiņas skaitītājs ir 4, tāpēc mēs ejam
saglabāt vēlreiz atkārtojot šo procesu.
>> Mēs ejam, lai atjaunotu mijmaiņas skaitītāju līdz 0, un apskatīt katru blakus pāri.
Tātad sākam ar 2 un 1-- viņi iziet no ierindas, tāpēc mēs mijmaiņas tiem
un mēs pievienot 1 līdz swap letes.
2 un 3, viņi kārtībā.
Mums nav nepieciešams neko darīt.
3 un 5 ir kārtībā.
Mums nav nepieciešams neko darīt tur.
>> 5 un 4, tie ir ārā no ierindas, un tāpēc mēs
nepieciešams, lai mijmaiņas tiem un pievienot 1 uz mijmaiņas letes.
Un tagad mēs esam pārvietoti 5, nākamais lielākais elements,
līdz beigām nešķirotu porciju.
Tātad, mēs tagad var zvanīt, ka daļa sakārtoti porciju.
>> Tagad jūs meklējat pie ekrāns un, iespējams, var pateikt,
kā es varu, ka masīva ir sakārtots tieši tagad.
Bet mēs nevaram pierādīt, ka vēl.
Mums nav garantija ka tas ir sakārtoti.
Bet tas ir, ja mijmaiņas counter gatavojas stāties spēlēt.
>> Tāpēc mēs esam pabeiguši caurlaidi.
Mijmaiņas skaitītājs ir 2.
Tātad mēs ejam atkārtot šis process atkal,
atkārto, līdz mijmaiņas skaitītājs ir 0.
Reset mijmaiņas skaitītāju uz 0.
Tātad mēs atjaunotu to.
>> Tagad apskatīt katru blakus 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ātad šajā brīdī, paziņojums mēs esam pabeiguši Aplūkojot katru blakus pāri,
bet mijmaiņas skaitītājs joprojām 0.
>> Ja mums nav, lai pārslēgtos kādi elementi, tad tie
ir jābūt kārtībā, ko pamatojoties uz šo procesu.
Un tā Lietderības koeficients veidu, Ka mēs datorzinātnieku mīlam,
ir, mēs tagad varam paziņot, visam blokam jābūt
sakārtots, jo mēs neesam ir swap kādi elementi.
Tas ir diezgan jauki.
>> Tātad, kas ir sliktākais gadījums scenārijs ar burbuļu veida?
Sliktākajā gadījumā masīvs ir pilnīgi apgrieztā secībā,
un tāpēc mums ir burbulis katram no lielajiem elementiem visu
ceļu pāri masīvs.
Un mums faktiski ir arī burbulis visi no mazo elementu atpakaļ
visu ceļu pāri masīvs, too.
Tātad, katrs no n elementiem ir, lai pārvietotos pāri visiem citiem n elementiem.
Tātad tas ir sliktākais scenārijs.
Labākajā gadījumā scenārijs, lai gan, tas ir
nedaudz atšķiras no atlases veida.
Masīvs ir jau sakārtots, kad mēs iet.
Mums nav nekādas mijmaiņas darījumi par pirmo caurlaide.
Tātad mēs varētu būt jāmeklē pie mazāk elementiem, vai ne?
Mums nav jāatkārto šis apstrādāt vairākas reizes.
>> Tātad, ko tas nozīmē?
Tātad, kas ir sliktākais scenārijs burbuļu veida, un to, kas ir
Labākajā gadījumā burbulis kārtot?
Vai jūs uzminēt šo?
Sliktākajā gadījumā, jums ir atkārtot visās n elementiem n reizes.
Tātad sliktākajā gadījumā ir n brusas.
>> Ja masīvs ir pilnīgi šķiroto gan, jums ir tikai
ir jāskatās uz katru no elementiem vienu reizi.
Un, ja mijmaiņas skaitītājs joprojām ir 0, Jūs varat teikt, tas masīvs ir sakārtots.
Un tā labākajā gadījumā, tas ir tiešām labāk nekā atlases
sort-- tas ir omega n.
>> Es esmu Doug Lloyd.
Tas ir CS50.