[Přehrávání hudby] 

DOUG LLOYD: Takže insertion sort je jiný Algoritmus můžeme použít pro třídění pole. Smyslem tohoto algoritmu je budovat své seřazené pole v místě, řazení prvků z způsob, jak jdete, aby uvolnily místo. To je mírně odlišný od výběru druhu nebo bublina třídění, například tam, kde jsme úpravě místa, kde děláme swapy. 

V tomto případě jsme, co se vlastně dělá, je posuvné prvky nad, z cesty. Jak tento algoritmus práce v pseudokódu? No řekněme, svévolně říci, že První prvek pole je seřazeny. Stavíme na místě. 

Budeme jít jeden prvek v čase a stavět to, a tak první věc, kterou vidíme, je jedním z prvků pole. A samozřejmě, jeden Prvek pole je tříděn. 

Pak budeme tento proces opakovat until-- budeme opakovat následující postup dokud se všechny prvky jsou seřazeny. Podívejte se na další netříděný prvku a vložte ji do tříděného části, posunutím požadované číslo prvků z cesty. Doufejme, že to vizualizace vám pomůže vidět přesně to, co je se děje s vkládací druhu. 

Takže znovu, tady je naše Celý netříděný pole, všechny prvky uvedené v červené barvě. A pojďme následujte kroky našeho pseudokódu. První věc, kterou děláme, je nazýváme První prvek pole, třídit. Takže jsme jen chtěl říct pět, nyní jste třídit. 

Pak se podíváme na další netříděný prvek pole a chceme vložit, že do seřazené části, tím, že přesouvá prvků nad. Takže dvou je další netříděného prvek pole. Je zřejmé, že před tím, než patří pět, takže to, co budeme dělat je druh držet dvou stranou na vteřinu, přesunout pět nad, a pak vložte dvě před pátou, kam by měl jít. A nyní můžeme říci, že dva jsou seřazeny. 

Takže jak vidíte, máme jenom tak daleko se podíval na dva prvky pole. Ještě jsme se podíval na odpočinku vůbec, ale my jsme mám tyto dva prvky řazeny podle způsob řadicí mechanismus. 

Takže jsme opět proces opakovat. Podívejte se na další netříděného element, to je jeden. Pojďme si myslí, že stranou na vteřinu, posunout vše nad a dal jeden pokud by mělo jít. 

Opět platí, stále jsme jen někdy Podíval se na jeden, dva a pět. Nevíme, co ještě přijde, ale my jsme řazeny tyto tři prvky. 

Další netříděný prvkem je tři, takže budeme ji stranou. Budeme posun nad to, co jsme je třeba, na které, tentokrát není všechno, jak v předchozím dva případy, je to jen pět. A pak budeme držet tři v, mezi dvěma a pěti. 

Šest je další netříděného element k poli. A ve skutečnosti šesti je větší než pět, tak my ani nemusíte dělat žádné odkládání. Můžeme jen připnout šest vpravo na konec seřazené části. 

A konečně, čtyři je Poslední netříděný element. Tak jsme to stranou, PŘEEXPONOVÁNO prvky musíme přejít přes, a pak dal čtyři tam, kam patří. A teď se podívej, máme sort všech prvků. Všimněte si, s vložením třídění, jsme neměli jít tam a zpět přes pole. Šli jsme jen přes pole jednou, a my posunul věci že bychom již setkali, aby aby se uvolnilo místo pro nové prvky. 

Takže to, co je nejhorší případ Scénář s vložení druhem? V nejhorším případě se pole je v opačném pořadí. Musíte přesunout každý z n prvků až do polohy N, pokaždé jsme provést vložení. To je hodně posouvání. 

V nejlepším případě se Pole je dokonale seřazeny. A něco jako, co se stalo s pěti a šesti v příkladu, kde jsme mohli jen připínáček to na aniž by bylo nutné dělat žádné řazení, bychom v podstatě dělat. 

Pokud si představit, že naše Pole byla jedna až šest, bychom začít tím, prohlašuje jeden je tříděn. Dva přichází poté, co jeden, takže můžeme jen říkat, OK, dobře jedna a dvě jsou seřazeny. Tři přichází po dvou tak, OK, jedna a dvě a tři jsou seřazeny. 

Nejsme jakýmkoliv swapy, my jsme Jen pohybující se tento řádek libovolný mezi tříděny a netříděné, jak jsme jít. Jak efektivně, jako jsme to udělali v příkladu, soustružení prvky modré, jak budeme postupovat. Takže to, co je nejhorší případ runtime, pak? Pamatujte si, že pokud budeme muset přesunout každý z na n prvky případně n pozice, doufejme, že vám dává idea, že nejhorší případ runtime je velký O n na druhou. 

V případě, že pole je dokonale řazeny, vše, co musíte udělat, je podívat se na každé jednotlivé součásti jednou, a pak jsme hotovi. Takže v nejlepším případě je to omega n. 

Jsem Doug Lloyd. To je CS50.