[Muzikos grojimo] 

Doug LLOYD: Taigi įterpimo Rūšiuoti kitas algoritmas mes galime naudoti rūšiuoti masyvą. Už šio algoritmo idėja yra sukurti savo rūšiuotą masyvo vietoje, perkeliant elementus iš būdas, kaip jūs einate, kad paliktume vietos. Tai yra šiek tiek kitoks nuo atrankos rūšiuoti ar burbulo rūšiuoti, pavyzdžiui, kur mes koreguojant vietas, kur mes darome apsikeitimo sandoriais. 

Šiuo atveju tai, ką mes iš tikrųjų darote, yra stumdomas elementai daugiau, iš kelio. Kaip veikia šį algoritmą dirbti Pseudocode? Na tegul tiesiog pasakyti, kad savavališkai Pirmasis elementas masyve yra rūšiuojami. Mes statome jį į vietą. 

Mes gonna go vieną elementą vienu metu ir statyti, todėl pirmas dalykas, kurį mes matome yra vienas elementas, masyvo. Ir pagal apibrėžimą, vienas elementas masyvas surūšiuotas. 

Tada mes šį procesą pakartoti until-- mes pakartoti šią procedūrą tol, kol visus elementus, yra rūšiuojami. Pažvelkite į kitą nerūšiuotų elemento ir įdėkite ją į rūšiuotų dalį, perkeliant reikiamą skaičių iš elementų, iš kelio. Tikimės, kad šis vizualizacija padės jums pamatyti, ką tai vyksta su įterpimo rūšiuoti. 

Taigi dar kartą, čia mūsų Visa nerūšiuotos masyvas, visus elementus, raudonai nurodyta. Ir tegul sekti žingsniai mūsų Pseudocode. Pirmas dalykas, kurį mes darome, yra mes vadiname pirmasis elementas masyvo, rūšiuojami. Taigi mes tiesiog sakys penki, jūs dabar rūšiuojami. 

Tada mes pažvelgti į kitą nerūšiuotų elementas masyve ir mes norime įrašyti, kad į rūšiuojami dalį, perkeliant elementus virš. Taigi du yra šalia nerūšiuotų elementas masyve. Akivaizdu, kad jis priklauso iki penki, todėl tai, ką mes darysim yra tarsi surengti du skirta per sekundę, pereiti penkis daugiau, ir tada įdėkite du prieš penkis, kur reikia eiti. Ir dabar mes galime pasakyti, kad du yra rūšiuojami. 

Taigi, kaip matote, mes tik tiek, kiek pažvelgė dviejų elementų masyvą. Mes ne pažvelgė poilsio ne visi, bet mes gavo šie du elementai surūšiuoti pagal būdas perjungimo mechanizmą. 

Taigi, mes vėl pakartokite šį procesą. Pažvelkite į kitą nerūšiuotų elementas, tai viena. Leiskite nuspręsti, kad skirta per sekundę, pereiti viską daugiau, ir įdėti vieną kur jis turėtų eiti. 

Vėlgi, vis tiek, mes tik kada nors pažvelgė į vieno, dviejų, ir penkių. Mes nežinome, ką dar ateina, bet mes surūšiuoti šių trijų elementų. 

Kitas nerūšiuotos elementas yra trys, todėl mes jį panaikinti. Mes pereinama, ką mes reikia, į kurią, šį kartą tai dar ne viskas, kaip ir ankstesnis du atvejai, tai tik penki. Ir tada mes klijuoti trys, tarp dviejų ir penkių. 

Šeši yra šalia nerūšiuotų elementas masyve. Ir iš tikrųjų šešių yra daugiau kaip penki, todėl mes net nereikia daryti jokio Swapping. Mes galime tik smeigtuko šeši dešinę į iš išrūšiuotų porcija pabaiga. 

Galiausiai, keturi yra paskutinis nerūšiuotos elementas. Taigi mes jį panaikinti, pereinama elementai turime pereiti per, ir tada įdėti keturis, jei ji priklauso. Ir dabar atrodo, mes tarsi iš visų elementų. Atkreipkite dėmesį, su įterpimo Rūšiuoti, mes neturėjome eiti pirmyn ir atgal per masyvo. Mes tik perėjo iš masyvo vieną kartą, ir mes persikėlė dalykus kad mes jau norime susidūrė, siekiant padaryti kambarį už naujų elementų. 

Taigi, kas blogiausiu atveju scenarijus su įterpimo rūšiuoti? Blogiausiu atveju, masyvas yra atvirkštine tvarka. Turite pereiti kiekvieną iš N elementų iki n pozicijų, kiekvieną kartą, kai mes padaryti įdėjimo. Štai iš perkeliant daug. 

Geriausiu atveju, array puikiai rūšiuojami. Ir tarsi kas atsitiko su penkių ir šešių pavyzdyje, kur mes galėtume tiesiog ant smeigtuko be daryti bet kokį perjungimą, mes norime iš esmės padaryti. 

Jei jūs galite įsivaizduoti, kad mūsų masyvas buvo vienas per šešių, mes norime pradėti nuo deklaruojant viena yra rūšiuojami. Du ateina po vieną, kad mes galime tik sako, gerai, gerai vieno ir dviejų rūšiuojami. Trys ateina po du taip, gerai, vieno ir dviejų ir trijų rūšiuojami. 

Mes ne priimant bet kokius sandorius, mes tiesiog perkeldami savavališkai linija tarp rūšiuotus ir nerūšiuotus, kaip mes einame. Taip efektyviai, kaip mes padarėme, pavyzdžiui, tekinimo elementus mėlyna, kaip mes toliau. Taigi, kas blogiausiu atveju Runtime, tada? Atminkite, kad jei mes turime pereiti kiekvieną iš kad n elementų galbūt n pozicijos, tikiuosi, kad tau duoda idėja, kad blogiausiu atveju Runtime yra Big O n kvadratu. 

Jei masyvas yra puikiai rūšiuojamos, visi mes turime daryti yra pažvelgti kiekvieną elementą vieną kartą, ir tada mes baigsite. Taigi geriausiu atveju, tai omega n. 

Aš Doug Lloyd. Tai CS50.