[Powered by Google Translate] [Lisätään Lajittele] [Tommy MacWilliam] [Harvardin yliopisto] [Tämä on CS50.TV] Katsotaanpa katsomaan lisäys lajitella algoritmi ottaa listan numeroiden ja lajittelusta. Algoritmi, muistan, on yksinkertaisesti askel-askeleelta menettely toteutuksessa tehtävään. Perusajatuksena lisäys lajitella, on jakaa meidän listan kahteen osaan, lajitellaan osa ja lajittelemattoman osan. 

Jokaisessa vaiheessa algoritmi, numero on siirretty alkaen lajittelemattoman osuuden lajiteltu osaan kunnes lopulta koko lajitellaan. Tässä on luettelo kuusi lajittelemattoman numerot - 23, 42, 4, 16, 8, ja 15. Koska nämä luvut eivät ole kaikki nousevassa järjestyksessä, he lajittelematta. Koska emme ole alkaneet lajittelu vielä, me harkita kaikkia kuutta osa meidän lajittelemattoman osan. 

Kun alamme lajittelu, laitamme nämä lajitellaan numerot vasemmalle näitä. Joten Aloitetaan 23, ensimmäinen elementti listalta. Meillä ei ole mitään elementtejä meidän lajiteltu osaan vielä, joten katsotaanpa yksinkertaisesti pitävät 23 on alku ja loppu meidän lajiteltu osan. Nyt meidän lajiteltu osa on yksi numero, 23, ja meidän lajittelemattoman osa on nämä viisi numeroa. Katsotaanpa nyt laittamaan seuraavan numeron meidän lajittelemattoman osaan, 42, tulee lajitella osaan. 

Voit tehdä niin, meidän täytyy verrata 42 23 - ainoa osatekijä lajiteltu osassa toistaiseksi. Neljäkymmentäkaksi on suurempi kuin 23, joten voimme yksinkertaisesti liittää 42 loppuun on järjestetty osan luettelosta. Hienoa! Nyt meidän lajiteltu osassa on kaksi elementtiä, ja meidän lajittelemattoman osassa on neljä elementtiä. Joten, nyt on nyt siirtyä 4, seuraava osa lajittelemattoman osaan. Joten, jos tämä olisi sijoitettava lajiteltu osaan? 

Muista, me haluamme asettaa tämän numeron lajiteltu järjestyksessä joten meidän lajiteltu osa pysyy oikein lajitellaan aina. Jos asetamme 4 oikealla 42, niin lista tulee epäkunnossa. Joten, jatkakaamme liikkuu oikealta vasemmalle meidän lajitella osaan. Kun siirrymme, katsotaanpa siirtää kunkin numeron alas paikka tehdä tilaa uuden numeron. Okei, 4 on myös pienempi kuin 23, joten emme voi sijoittaa sen tässäkään. Siirrytään 23 oikea paikka. 

Tämä tarkoittaa haluaisimme sijoittaa 4 ensimmäiseen aukkoon lajiteltu osaan. Huomaa, miten tämä tila luettelossa oli jo tyhjä, koska olemme siirtymässä lajiteltu elementtejä alas olemme kohdanneet heidät. Selvä. Joten olemme puolimatkassa. Jatketaan meidän algoritmi lisäämällä 16 osaksi lajiteltu osaan. Kuusitoista on alle 42, joten katsotaanpa siirtää 42 oikealle. Kuusitoista on myös pienempi kuin 23, joten katsotaanpa myös siirtää kyseistä tekijää. 

Nyt, 16 on suurempi kuin 4. Joten näyttää siltä, ​​haluaisimme lisätä 16 välillä 4 ja 23. Liikkuessaan lajiteltu osan luettelon oikealta vasemmalle, 4 on ensimmäinen numero olemme nähneet, joka on pienempi kuin määrä, yritämme lisätä. Joten, nyt voimme lisätä 16 tähän tyhjään paikkaan joka, muistakaa, olemme luonut liikkuvia osia lajitella osan yli kuten olemme kohdanneet heidät. 

Selvä. Nyt meillä on neljä lajiteltu elementtejä ja kaksi lajittelemattoman elementtejä. Joten, lähdetään 8 osaksi lajiteltu osaan. Kahdeksan on alle 42. Kahdeksan on vähemmän kuin 23. Ja 8 on alle 16. Mutta 8 on suurempi kuin 4. Joten haluaisimme lisätä 8 välillä 4 ja 16. Ja nyt meillä on vain yksi elementti jäljellä lajitella - 15. Viisitoista on vähemmän kuin 42, Viisitoista on vähemmän kuin 23. Ja 15 on alle 16. Mutta 15 on suurempi kuin 8. 

Niin, tässä on, jos haluamme tehdä meidän lopullinen paikoilleen. Ja olemme tehneet. Meillä ei ole enempää elementtejä lajittelemattoman osaan, ja meidän lajitellaan osa on oikeassa järjestyksessä. Numerot ovat järjesteltyinä pienimmästä suurimpaan. Joten sallikaa katsomaan joitakin pseudokoodi joka kuvaa vaiheita me juuri suoritettu. 

On line 1, voimme nähdä, että meidän täytyy toistaa kullakin elementti luettelossa paitsi ensimmäinen, koska ensimmäinen elementti lajittelemattoman osaan tulee yksinkertaisesti ensimmäinen elementti on lajiteltu osaan. Riveillä 2 ja 3, olemme tarkkailemalla nykyiseen paikka lajittelemattoman osaan. Elementti edustaa numero parhaillaan siirtymässä lajiteltu osaan, ja j edustaa indeksinä lajittelemattoman osaan. 

On line 4, olemme iteroimalla läpi lajiteltu osan oikealta vasemmalle. Haluamme pysäyttää iteroimalla kerran elementin vasemmalle nykyiseen aseman on pienempi kuin elementin yritämme lisätä. Riviltä 5, olemme siirtymässä jokainen elementti kohtaamme yhden askeleen oikealle. Näin meillä on selkeä tila, joka lisätään, kun löydämme ensimmäinen osa vähemmän kuin elementti liikumme. Rivillä 6, me päivitämme vastoin edelleen siirtyä vasemmalle läpi lajiteltu osan. Lopuksi, rivillä 7, me työntämällä elementin lajiteltu osan luettelosta. 

Tiedämme, että se on okei lisätä asentoon j, koska olemme jo siirtyneet elementti, joka aiemmin olemassa yksi tilaa oikealle. Muista, liikumme läpi lajiteltu osan oikealta vasemmalle, mutta olemme siirtymässä läpi lajittelemattoman osan vasemmalta oikealle. Selvä. Katsotaanpa nyt katsomaan kuinka kauan käynnissä, että algoritmi kesti. Meillä tulee ensin kysyä, kuinka kauan kestää tämä algoritmi ajaa pahimmassa tapauksessa. Muistutan, että me edustamme tällä käyntiaika Big O notaatio. Jotta lajitella listalta, jouduimme iteroida yli elementtejä lajittelemattoman osaan, ja jokainen näistä seikoista, mahdollisesti kaikkien elementtien lajiteltu osaan. Intuitiivisesti tämä kuulostaa O (n ^ 2) toiminta. 

Tarkasteltaessa meidän pseudokoodilla, meillä on silmukka sisäkkäin toisen silmukan, joka todellakin kuulostaa O (n ^ 2) toimintaa. Kuitenkin lajiteltu osa listasta ei sisältänyt koko listan loppuun asti. Silti voisimme mahdollisesti lisätään uusi elementti alusta lajiteltu osan joka iterointia algoritmi, mikä tarkoittaa, että meidän täytyisi katsoa jokaisen elementin hetkellä lajiteltu osaan. Niin, se tarkoittaa, että voisimme mahdollisesti tehdä yksi vertailu toinen elementti, kaksi vertailua varten kolmas elementti, ja niin edelleen. Niin, että vaiheiden kokonaismäärä on summa kokonaisluvut 1 listan pituus miinus 1. Voimme edustaa tämän kanssa summattu. 

Emme aio mennä summaussarjojen täällä, mutta näyttää siltä, ​​että tämä summattu vastaa n (n - 1) yli 2, joka vastaa n ^ 2/2 - n / 2. Kun puhutaan asymptoottinen runtime, tämä n ^ 2 termi tulee hallitsemaan tätä n. aikavälillä. Niin, lisäys sort on Big O (n ^ 2). Mitä jos me juoksi lisäys lajitella jo lajiteltu luettelo. Tässä tapauksessa, olimme yksinkertaisesti rakentaa lajiteltu osan vasemmalta oikealle. Joten me vain tarvitsemme määräyksestä n askelta. 

Tämä tarkoittaa, että lisäys tavallaan on parhaassa tapauksessa suorituskyvyn n, jota edustavat kanssa Ω (n). Ja se on siinä asetettavaksi lajitella, vain yksi monista algoritmien voimme käyttää lajittelemaan lista. Nimeni on Tommy, ja tämä on CS50. [CS50.TV] Voi, et vain voi lopettaa, että kun se alkaa. Voi, teimme että - >> Boom!