[Glazbom] 

Doug LLOYD: Pa umetanje vrsta je još algoritam možemo koristiti za sortiranje niz. Ideja iza ovog algoritma je izgraditi sortirani niz na mjestu, kreće elemente iz onako kao što ide, kako bi napravili mjesta. To je malo drugačiji od odabira vrste ili mjehura vrsta, na primjer, gdje mi smo podešavanjem mjesta, gdje smo stvaranje swap. 

U tom slučaju ono što smo zapravo radite je klizni elementi više, zabit. Kako ovo algoritam rad u pseudokod? Pa neka je samo reći da je samovoljno Prvi element niza je riješeno. Mi smo ga gradi na mjestu. 

Mi ćemo ići jedan element u isto vrijeme i graditi ga, pa je prva stvar koju smo vidjeli je jedan element polje. A po definiciji, jedan Element niz sortira. 

Onda ćemo ponoviti ovaj postupak until-- ćemo ponoviti sljedeći postupak dok su svi elementi razvrstani. Pogledajte sljedeću nerazvrstani elementa i umetnite ga u sortiranog dijela, pomicanjem potreban broj elemenata zabit. Nadam se da ovo vizualizacija će vam pomoći da vidite točno ono što je događa s umetanja vrste. 

Pa opet, ovdje je naš Cijeli niz Nesortirano, svi elementi navedeno u crveno. I neka je slijede koraci našeg pseudokod. Prva stvar koju radimo, je zovemo Prvi element polja, sortirati. Dakle, mi smo samo ću reći pet, sad ste razvrstani. 

Onda mi gledamo na sljedeći nesortirani element polja i želimo umetnuti da u sortirane dijela, pomicanjem elemenata više. Dakle, dva je sljedeći nesortiran element polja. Jasno mu je i mjesto prije pet, pa što ćemo učiniti je vrsta držite dva stranu za trenutak, pomak pet, a potom umetnite dva Prije pet, gdje bi trebao ići. I sada možemo reći da su dva je riješeno. 

Dakle, kao što možete vidjeti, mi smo samo dosad pogledao dva elementa niza. Nismo izgledao odmor na sve, ali smo dobio ta dva elementa razvrstani prema način pomicanja mehanizma. 

Tako smo opet ponoviti postupak. Pogledajte sljedeći nesortiran Element, to je jedan. Idemo drže da na stranu za trenutak, pomak sve više, i staviti jedan gdje bi trebao ići. 

Opet, i dalje, mi smo jedini ikada pogledao jedan, dva i pet. Mi ne znamo što drugo dolazi, ali smo razvrstani one tri elementa. 

Sljedeća Nesortirano element tri, pa ćemo ga staviti na stranu. Mi ćemo pomak na ono što smo potrebno je što, ovaj put nije sve kao u prethodnom dva slučaja, to je samo pet. A onda ćemo se držati tri u, između dva i pet. 

Šest je sljedeći nesortiran element polja. A u stvari šest je veći od pet, pa mi ni ne morate to učiniti bilo zamjene. Mi samo možemo sklepati šest pravo na kraj dijela poredanih. 

Konačno, četiri je Posljednji Nesortirano elementa. Tako ćemo ga staviti na stranu, pomak tijekom elementi moramo prebaciti preko, a zatim staviti četiri, gdje mu je i mjesto. A sada pogledajte, mi smo vrsta svih elemenata. Obavijest s umetanjem vrsta, nismo imali ići naprijed i natrag preko polja. Mi išli samo preko polja jedno vrijeme i pomaknuo se stvari da bismo već naišli, kako kako bi napravili mjesta za nove elemente. 

Dakle, što je najgori slučaj Scenarij s umetanjem vrste? U najgorem slučaju, Niz je u obrnutom redoslijedu. Morate pomak svaki od n elemenata do n pozicija, svaki put kad smo napraviti umetanje. To je puno pomicanja. 

U najboljem slučaju, Niz je savršeno razvrstani. A nešto poput onoga što se dogodilo s pet i šest u, primjerice, gdje smo samo mogli pričvrstiti na bez potrebe za bilo kakvo pomicanje, mi u biti ne bih učinio. 

Ako zamislite da je naš Niz je jedan do šest, ćemo krenuti izjavljujući jedan je riješeno. Dva dolazi nakon jednog tako možemo jednostavno kažu, u redu, ali jedan i dva su razvrstani. Tri dolazi nakon dva tako, u redu, jedan i dva i tri su razvrstani. 

Mi ne čineći nikakve zamjene, mi smo Upravo kreće ovu proizvoljnu crtu između razvrstani i Nesortirano kako idemo. Jednako učinkovito kao što smo učinili u primjeru, okrećući elemente plava, kao što smo nastavili. Dakle, što je najgori slučaj izvođenja, onda? Zapamtite, ako imamo pomak svake od su n elemenata n eventualno pozicije, nadam se da vam daje ideja da je najgori slučaj Runtime je Big O n na kvadrat. 

Ako je niz savršeno razvrstani, sve što morate učiniti je pogledate svakog pojedinog elementa jednom, a onda smo gotovi. Dakle, u najboljem slučaju, to je omega n. 

Ja sam Doug Lloyd. Ovo je CS50.