>> [Mūzikas atskaņošanai]
>> Doug LLOYD: Tātad ievietošanas kārtošanas ir cits algoritmu mēs varam izmantot, lai sakārtotu masīvu.
Ideja šo algoritmu ir veidot savu sakārtoti masīvs
vietā, novirzot elementus no veids, kā jums iet, lai padarītu telpu.
Tas ir nedaudz atšķirīgs no atlases veida vai burbuļa
veida, piemēram, kur mēs esam pielāgojot vietas,
kur mēs nesam mijmaiņas darījumus.
>> Šajā gadījumā tas, ko mēs esam patiesībā dara, ir bīdāmās elementi
vairāk, no tā.
Kā šo algoritmu strādāt pseudocode?
Nu pieņemsim tikai patvaļīgi teikt, ka masīva pirmais elements ir sakārtots.
Mēs esam ēka to vietā.
>> Mēs esam gonna iet vienu elementu laikā un veidot tā, un tā ir pirmā lieta, ko mēs redzam
ir viens no elementiem masīvs.
Un pēc definīcijas, viena elements masīvs ir sakārtots.
>> Tad mēs atkārtot šo procesu until-- mēs atkārtot šādu procesu
līdz visi no elementiem, kas ir sakārtoti.
Paskaties nākamajā nešķirotu elementu un ievietojiet to šķiroto daļu,
pārvietojot vajadzīgo skaitu elementu no tā.
Cerams, ka šī vizualizācija palīdzēs jums redzēt tieši to, kas ir
notiek ar ievietošanas veida.
>> Tātad atkal, šeit ir mūsu Visa nešķiroti masīvs,
visus elementus, kas norādīts sarkanā krāsā.
Un pieņemsim sekot soļi mūsu pseudocode.
Pirmā lieta, ko mēs darām, ir mēs saucam masīva pirmais elements, sakārtoti.
Tātad mēs esam tikai gonna teiksim pieci, jūs tagad sakārtoti.
>> Tad mēs skatāmies uz nākamo nešķiroti elements masīva
un mēs vēlamies, lai ievietotu, ka uz sakārtoti daļu,
pārvietojot elementus pāri.
Tātad divi ir nākamais nešķiroti masīva elements.
Nepārprotami tas pieder, pirms pieci, lai to, ko mēs esam gonna do
ir sava veida turēt divus malā uz otru, pāriet pieci pāri, un pēc tam ievietot divas
Pirms pieciem, kur jāiet.
Un tagad mēs varam teikt, ka divi ir sakārtots.
>> Tātad, kā jūs varat redzēt, mēs esam tikai tik tālu paskatījās diviem elementiem masīva.
Mēs neesam paskatījās atpūsties vispār, bet mēs esam
got šie divi elementi sakārtoti pēc veids pārslēgšanas mehānisma.
>> Tātad mēs atkal atkārtojiet procesu.
Paskaties nākamajā nešķiroti elements, tas ir viens.
Pieņemsim, ka tur malā uz otru, novirzīt visu vairāk, un ievietojiet vienu
kur tam vajadzētu iet.
>> Atkal, tomēr, mēs esam tikai kādreiz paskatījās viens, divi, un pieci.
Mēs nezinām, ko vēl nāk, bet mēs esam sakārtots šos trīs elementus.
>> Nākamais nešķiroti elements ir trīs, tāpēc mēs noteikti to malā.
Mēs novirzīt vairāk nekā to, ko mēs ir nepieciešams, kas, šoreiz
nav viss kā iepriekšējā divas lietas, tas ir tikai pieci.
Un tad mēs stick trim, starp diviem un pieciem.
>> Seši ir nākamais nešķiroti elements masīva.
Un faktiski seši ir lielāks par pieciem, lai mums nav pat nepieciešams veikt nekādas pārnešana.
Mēs varam tikai sadiegšana sešas tiesības uz beigas sakārtoti porciju.
>> Visbeidzot, četri ir pēdējais nešķiroti elements.
Tāpēc mēs noteikti to malā, novirzīt vairāk elementi mums ir nepieciešams pāriet pāri,
un pēc tam nodot četras kur tā pieder.
Un tagad izskatās, mēs esam sava veida no visiem elementiem.
Ievērojiet ar ievietošanas kārtot, mums nebija
iet uz priekšu un atpakaļ pāri masīvs.
Mēs tikai gāja pāri masīvs vienu reizi, un mēs pārvietoti lietas
ka mēs gribētu jau radušās, lai lai atbrīvotu vietu jauniem elementiem.
>> Tātad, kas ir sliktākais gadījums scenārijs ar ievietošanas kārtošanas?
Sliktākajā gadījumā masīvs ir apgrieztā secībā.
Jums ir novirzīt katru no n elementiem līdz n pozīcijām, katru reizi, kad mēs
veikt ievietošanu.
Tas ir daudz novirzot.
>> Labākajā gadījumā masīvs ir perfekti sakārtots.
Un veida, piemēram, to, kas notika ar pieciem un sešiem piemērā,
kur mēs varētu vienkārši sadiegšana to bez darīt jebkuru pārnesi,
mēs gribētu būtībā darīt.
>> Ja jūs varat iedomāties, ka mūsu masīvs bija viens pa sešiem,
mēs gribētu sākt, pasludina vienu, ir sakārtots.
Divi nāk pēc viena tāpēc mēs varam tikai teikt, OK, arī viens un divi ir sakārtoti.
Trīs nāk pēc diviem tā, OK, viens un divi, un trīs ir sakārtoti.
>> Mēs esam ne nekādus mijmaiņas darījumus, mēs esam tikai pārvietojas šo patvaļīgu līniju
starp sašķiroti un šķirotas, kā mums iet.
Tikpat efektīvi kā mēs to darījām piemērā, pagriežot elementus zils, kā mēs turpināt.
Tātad, kas ir sliktākajā gadījumā runtime, tad?
Atcerieties, ja mums ir novirzīt katru no tad n elementus iespējams n pozīcijas,
cerams, ka dod jums ideja, ka sliktākajā gadījumā
runtime ir Big O n brusas.
>> Ja masīvs ir pilnīgi sakārtots, viss, kas mums ir jādara
ir apskatīt katru elementu vienreiz, un tad mēs esam darījuši.
Tātad labākajā gadījumā, tas ir omega n.
>> Es esmu Doug Lloyd.
Tas ir CS50.