[Musiikkia] 

DOUG Lloyd: Niin lisäyslajittelun on toinen algoritmi voimme käyttää järjestellä jono. Ajatuksena algoritmi on rakentaa lajitellut array paikallaan, siirtää elementtejä ulos Muuten kuten mennä, tehdä tilaa. Tämä on hieman erilainen valinnasta lajitella tai kupla lajitella, esimerkiksi silloin, kun olemme säätämällä paikoissa, jossa Teemme swap. 

Tässä tapauksessa, mitä olemme todella teet on liukuelementit yli, pois tieltä. Miten tämä algoritmi työskennellä pseudokoodilla? No sanotaan nyt mielivaltaisesti sanoa, että ensimmäinen alkiota lajitellaan. Me rakennamme sitä paikallaan. 

Aiomme mennä yksi osa kerrallaan ja rakentaa, ja niin ensimmäinen asia näemme on yksi elementti array. Ja määritelmän, yksi alkiotaulukko lajitellaan. 

Sitten me toista tämä prosessi until-- me toista seuraavista prosessin kunnes kaikki elementit lajitellaan. Katso seuraava lajittelemattoman elementti ja aseta se lajitellut osaan, siirtämällä tarvittava määrä elementtien pois tieltä. Toivottavasti tämä visualisointi auttaa sinua nähdä, mitä on meneillään kanssa lisäyslajittelun. 

Joten jälleen, tässä on meidän koko lajittelemattomat array, kaikki elementit merkitty punaisella. Ja nyt seurata vaiheet meidän pseudokoodin. Ensimmäinen asia teemme, on kutsumme ensimmäinen alkiota, lajiteltu. Joten olemme vain aio sanoa viisi, olet nyt lajitellaan. 

Sitten katsomme seuraavan lajittelematon alkio ja haluamme lisätä, että osaksi lajiteltu osaan, siirtämällä elementtien yli. Joten kaksi on seuraava lajittelematonta alkiota. Selvästi se kuuluu ennen viisi, joten mitä aiomme tehdä on tavallaan järjestää kaksi varattu toisen, siirtää viisi yli, ja aseta kaksi ennen viisi, minne pitäisi mennä. Ja nyt voimme sanoa, että kaksi on lajiteltu. 

Joten kuten näette, olemme vain toistaiseksi tarkasteli kahta elementtejä jono. Emme ole katsonut levätä ollenkaan, mutta olemme mutta nämä kaksi elementtiä lajiteltu tapa siirtyminen mekanismin. 

Joten me toista prosessi uudelleen. Katsokaa seuraava lajittelemattoman elementti, se on yksi. Katsotaanpa katsonut, että syrjään toisen, siirtää kaikki yli, ja laita yksi jos se pitäisi mennä. 

Jälleen edelleen, olemme aina vain katsoi yksi, kaksi ja viisi. Emme tiedä mitä muuta on tulossa, mutta olemme lajiteltu näistä kolmesta. 

Seuraava lajittelemattomat elementti on kolme, joten me aseta se sivuun. Me siirtää, mitä me täytyy joka tällä kertaa ei ole kaikki kuten edellisessä kaksi tapausta, se on vain viisi. Ja sitten me kiinni kolme, kahden ja viiden. 

Kuusi on seuraava lajittelematonta elementti array. Ja itse asiassa kuusi on suurempi kuin viisi, joten emme edes tarvitse tehdä mitään vaihtamista. Voimme vain tack kuusi oikealle ja loppuun järjestetty osan. 

Lopuksi neljä on viime lajittelemattomat elementti. Niin me sen syrjään, siirtää yli elementit meidän siirtää yli, ja sitten laittaa neljä minne se kuuluu. Ja nyt näyttää, olemme tavallaan kaikki tekijät. Huomaa insertiovektorilla lajitella, meillä ei ollut mennä edestakaisin jono. Me vain meni poikki array kerran, ja muutimme asiat että olimme jo kohdanneet, jotta tehdä tilaa uusia elementtejä. 

Niin mitä pahimmassa tapauksessa skenaario kanssa lisäyslajittelun? Pahimmassa tapauksessa, array on päinvastaisessa järjestyksessä. Sinun täytyy siirtää kunkin n elementtien jopa n kantoja, joka ikinen kerta me tehdä lisäys. Se on paljon siirtää. 

Parhaassa tapauksessa array on täydellisesti lajitellaan. Ja tavallaan kuin mitä tapahtui viisi ja kuusi esimerkissä, jossa voisimme vain tack sen ilman tehdä siirtyisi, olimme lähinnä tehdä. 

Jos kuvitella, että meidän array oli yksi läpi kuusi, alkaisimme pois julistamisesta yksi lajitellaan. Kaksi tulee yhden niin voimme vain sanovat, OK, hyvin yksi ja kaksi lajitellaan. Kolme tulee sen jälkeen kaksi niin, OK, yksi ja kaksi ja kolme lajitellaan. 

Emme teet mitään vaihtosopimukset, olemme vain liikkuvat tämä mielivaltainen linja välillä lajitellaan ja lajittelemattomat menemme. Yhtä tehokkaasti kuin teimme esimerkissä, Kääntöelimien sininen, kuten me edetä. Niin mitä pahimmassa tapauksessa runtime, sitten? Muista, jos meillä on siirtää kunkin n elementit mahdollisesti n kantoja, toivottavasti, joka antaa sinulle ajatus, että pahimmassa tapauksessa runtime on Big O n neliö. 

Jos matriisi on täysin lajiteltu, kaikki meidän on tehtävä on tarkastella jokaisen elementin kerran, ja sitten olemme tehneet. Joten parhaassa tapauksessa, se on omega n. 

Olen Doug Lloyd. Tämä on CS50.