>> [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.