[Prehrávanie hudby] 

DOUG LLOYD: Takže insertion sort je iný Algoritmus môžeme použiť pre triedenie poľa. Zmyslom tohto algoritmu je budovať svoje zoradené pole v mieste, radenie prvkov z spôsob, ako idete, aby uvoľnili miesto. To je mierne odlišný od výberu druhu alebo bublina triedenie, napríklad tam, kde sme úprave miesta, kde robíme swapy. 

V tomto prípade sme, čo sa vlastne robí, je posuvné prvky nad, z cestu. Ako tento algoritmus práce v pseudokódu? No povedzme, svojvoľne povedať, že Prvý prvok poľa je zoradené. Staviame na mieste. 

Budeme ísť jeden prvok v čase a stavať to, a tak prvá vec, ktorú vidíme, je jedným z prvkov poľa. A samozrejme, jeden Prvok poľa je triedený. 

Potom budeme tento proces opakovať until-- budeme opakovať nasledujúci postup kým sa všetky prvky sú zoradené. Pozrite sa na ďalšie netriedený prvku a vložte ju do triedeného časti, posunutím požadované číslo prvkov z cesty. Dúfajme, že to vizualizácia vám pomôže vidieť presne to, čo je sa deje s vkladacie druhu. 

Takže znovu, tu je naša Celý netriedený poľa, všetky prvky uvedené v červenej farbe. A poďme nasledujte kroky nášho pseudokódu. Prvá vec, ktorú robíme, je nazývame Prvý prvok poľa, triediť. Takže sme len chcel povedať päť, teraz ste triediť. 

Potom sa pozrieme na ďalšie netriedený prvok poľa a chceme vložiť, že do zoradené časti, tým, že presúva prvkov nad. Takže dvoch je ďalší netriedeného prvok poľa. Je zrejmé, že pred tým, než patrí päť, takže to, čo budeme robiť je druh držať dvoch stranou na sekundu, presunúť päť nad, a potom vložte dve pred piatou, kam by mal ísť. A teraz môžeme povedať, že dvaja sú zoradené. 

Takže ako vidíte, máme len tak ďaleko sa pozrel na dva prvky poľa. Ešte sme sa pozrel na odpočinku vôbec, ale my sme mám tieto dva prvky radené podľa spôsob radiacej mechanizmus. 

Takže sme opäť proces opakovať. Pozrite sa na ďalšie netriedeného element, to je jeden. Poďme si myslí, že stranou na sekundu, posunúť všetko nad a dal jeden ak by malo ísť. 

Opäť platí, stále sme len niekedy Pozrel sa na jeden, dva a päť. Nevieme, čo ešte príde, ale my sme radené tieto tri prvky. 

Ďalšie netriedený prvkom je tri, takže budeme ju bokom. Budeme posun nad to, čo sme je potrebné, na ktoré, tentoraz nie je všetko, ako v predchádzajúcom dva prípady, je to len päť. A potom budeme držať tri v, medzi dvoma a piatimi. 

Šesť je ďalší netriedeného element k poľu. A v skutočnosti šiestich je väčší ako päť, tak my ani nemusíte robiť žiadne odkladanie. Môžeme len pripnúť šesť vpravo na koniec zoradené časti. 

A konečne, štyri je Posledná netriedený element. Tak sme to stranou, preexponované prvky musíme prejsť cez, a potom dal štyri tam, kam patrí. A teraz sa pozri, máme sort všetkých prvkov. Všimnite si, s vložením triedenie, sme nemali ísť tam a späť cez pole. Šli sme len cez pole raz, a my posunul veci že by sme už stretli, aby aby sa uvoľnilo miesto pre nové prvky. 

Takže to, čo je najhorší prípad Scenár s vloženie druhom? V najhoršom prípade sa pole je v opačnom poradí. Musíte presunúť každý z n prvkov až do polohy N, zakaždým sme vykonať vloženie. To je veľa posúvanie. 

V najlepšom prípade sa Pole je dokonale zoradené. A niečo ako, čo sa stalo s piatimi a šiestimi v príklade, kde sme mohli len pripináčika to na aby bolo nutné robiť žiadne radenie, by sme v podstate robiť. 

Ak si predstaviť, že naše Poľa bola jedna až šesť, by sme začať tým, prehlasuje jeden je triedený. Dva prichádza potom, čo jeden, takže môžeme len hovoriť, OK, dobre jedna a dve sú zoradené. Tri prichádza po dvoch tak, OK, jedna a dve a tri sú zoradené. 

Nie sme akýmkoľvek swapy, my sme Len pohybujúce sa tento riadok ľubovoľný medzi triedené a netriedené, ako sme ísť. Ako efektívne, ako sme to urobili v príklade, sústruženie prvky modrej, ako budeme postupovať. Takže to, čo je najhorší prípad runtime, potom? Pamätajte si, že ak budeme musieť presunúť každý z na n prvky prípadne n pozície, dúfajme, že vám dáva idea, že najhorší prípad runtime je veľký O n na druhú. 

V prípade, že pole je dokonale radené, všetko, čo musíte urobiť, je pozrieť sa na každé jednotlivé súčasti raz, a potom sme hotoví. Takže v najlepšom prípade je to omega n. 

Som Doug Lloyd. To je CS50.