[Powered by Google Translate] TOMMY: Katsotaanpa katsomaan valikoima lajitella, algoritmi ottaa listan numeroiden ja lajittelusta. Algoritmi, muistan, on yksinkertaisesti askel-askeleelta menettely toteutuksessa tehtävä. Perusajatuksena valinta tavallaan on jakaa lista kahteen osaan - lajitellaan osa ja lajittelemattoman osan. Jokaisessa vaiheessa algoritmi, numero siirretään lajittelemattoman annoksena järjestetty osaan, kunnes lopulta koko lista on lajiteltu. Joten tässä on luettelo kuusi numeroa - 23, 42, 4, 16, 8, ja 15. Juuri nyt koko lista pidetään lajittelematta. Vaikka useita kuten 16 voi jo olla oikeassa sijainnin, algoritmi ei voi mitenkään tietää, että ennen koko lista on lajiteltu. Joten me miettiä jokaisen numeron lajittelemattomana kunnes lajitella sen itse. Me tiedämme, että haluamme luetteloa olla nousevassa järjestyksessä. Joten me haluamme rakentaa lajiteltu osa meidän listan vasemmalta oikealle, pienimmästä suurimpaan. Voit tehdä, että meidän täytyy löytää minimi lajittelemattoman elementti ja laita se lopussa lajiteltu osan. Koska luettelo ei ole lajiteltu, ainoa tapa tehdä se on näyttää jokaisen elementin lajittelemattoman osassa, muistaen joka elementti on alhaisin ja vertaamalla jokainen elementti siihen. Joten me ensin katsoa 23. Tämä on ensimmäinen osa olemme nähneet, niin me muistaa se minimi. Seuraavaksi tutustumme 42. 42 on suurempi kuin 23, niin 23 on edelleen pienin. Seuraavaksi on 4, joka on vähemmän kuin 23, joten muistamme 4 uutena minimi. Seuraava on 16, joka on suurempi kuin 4, niin 4 on edelleen pienin. 8 on suurempi kuin 4, ja 15 on suurempi kuin 4, niin 4 on oltava pienin lajittelemattoman elementti. Joten vaikka ihmisinä voimme heti nähdä, että 4 on pienin elementti, meidän algoritmi tarvitsee katsoa jokainen lajittelemattoman elementti, vaikka olemme löytäneet 4 - pienin alkio. Joten nyt olemme huomanneet pienin alkio, 4, me haluamme siirtää sen lajiteltu osan luettelossa. Koska tämä on ensimmäinen askel, tämä tarkoittaa sitä, emme halua laittaa 4: listan alkuun. Tällä hetkellä 23 on alussa luettelossa, joten Katsotaanpa vaihtaa 4 ja 23. Joten nyt lista näyttää tältä. Tiedämme, että 4 on sen lopullisessa sijainnin, koska se on sekä pienintä elementin ja elementin alussa luettelon. Tämä tarkoittaa, että meidän ei koskaan tarvitse siirtää uudelleen. Joten toistan tämän prosessin lisätä toisen elementin lajiteltu osan luettelosta. Me tiedämme, että meidän ei tarvitse katsoa 4, koska se on jo lajiteltu. Joten voimme aloittaa 42, jonka me muistan pienin alkio. Joten seuraavan me tarkastelemme 23, joka on alle 42, joten Muistan 23 on uusi minimi. Seuraava näemme 16, joka on pienempi kuin 23, niin 16 on uusi minimi. Nyt tarkastelemme 8, joka on pienempi kuin 16, niin 8 on uusi minimi. Ja lopuksi 8 on pienempi kuin 15, niin tiedetään, että 8 on vähimmäismäärä lajittelemattoman elementti. Joten se tarkoittaa, että meidän pitäisi liittää 8 lajiteltu osan luettelosta. Juuri nyt 4 on ainoa lajiteltu elementti, joten haluamme sijoittaa 8 vieressä 4. Koska 42 on ensimmäinen osa lajittelemattoman osa lista, me haluamme vaihtaa 42 ja 8. Joten nyt lista näyttää tältä. 4 ja 8 edustavat lajiteltu osan luettelosta, ja loput numerot edustavat lajittelemattoman osan luettelosta. Joten jatka toisen iteraation. Aloitamme 23 tällä kertaa, koska meidän ei tarvitse katsoa 4 ja 8 enää, koska he ovat jo lajiteltu. 16 on alle 23, niin me muistaa 16 uudeksi minimi. 16 on pienempi kuin 42, mutta 15 on pienempi kuin 16, niin 15 on oltava minimi lajittelemattoman elementti. Joten nyt haluamme vaihtaa 15 ja 23 meille tämä luettelo. Lajiteltu osa luettelo koostuu 4, 8 ja 15, ja Nämä elementit ovat edelleen lajittelematta. Mutta se vain niin, että seuraava lajittelemattoman elementti, 16, on jo järjestetty. Kuitenkaan ei ole mitään keinoa, jolla algoritmin tietää, että 16 on jo sen oikeaan paikkaan, joten tarvitsemme vielä toistaa täsmälleen saman prosessin. Niin näemme, että 16 on pienempi kuin 42, ja 16 on pienempi kuin 23, niin 16 on oltava vähintään elementti. On mahdotonta vaihtaa tätä elementtiä itsensä kanssa, joten voimme jätä se tähän paikkaan. Joten tarvitsemme yhden pass meidän algoritmin. 42 on suurempi kuin 23, niin 23 on oltava vähintään lajittelemattoman elementti. Kun me vaihtaa 23 ja 42, päädymme meidän lopullinen lajiteltu lista - 4, 8, 15, 16, 23, 42. Tiedämme 42 on oltava oikeassa paikassa, sillä se on Ainoa jäljellä, ja se valinta lajitella. Katsotaanpa nyt virallistaa meidän algoritmi joitakin pseudokoodi. Linjalla yksi, voimme nähdä, että meidän täytyy integroida yli jokainen elementti luettelosta. Paitsi viimeinen elementti, koska 1 elementti lista on jo järjestetty. Linjalla kaksi, pidämme ensimmäinen osa lajittelemattoman osa luettelo on minimi, kuten teimme kanssa Esimerkiksi, joten meillä on jotain verrata. Linjalla kolme alkaa toisen silmukan, jossa me iteroida yli jokainen lajittelemattoman elementti. Tiedämme, että kun olen iteraation, lajiteltu osa meidän Luettelossa on oltava i elementtejä sitä, koska kussakin vaiheessa lajittelee yksi elementti. Joten ensimmäinen lajittelemattoman elementin tulee olla asennossa I plus 1. On line neljä vertaamme nykyistä elementin minimi elementti, että olemme nähneet tähän mennessä. Jos nykyinen tekijä on pienempi kuin pienimmän elementti, niin me muistamme alkion uutena vähintään linjalla viisi. Lopuksi linjat kuusi ja seitsemän, me vaihtaa vähintään elementti ensimmäinen lajittelemattoman elementti, mikä lisäämällä se lajitellaan osan luettelosta. Kun meillä on algoritmi, tärkeää kysyä itsemme ohjelmoijat on kuinka kauan kesti, että kestää? Meillä tulee ensin kysyä, kuinka kauan se kestää tämän algoritmi ajaa pahimmassa tapauksessa? Muistan me edustamme tätä käynnissä aika iso O notaatio. Jotta voitaisiin määrittää minimi lajittelemattoman elementti, me lähinnä oli vertailla jokainen alkio luettelossa joka toinen elementti luettelossa. Intuitiivisesti tämä kuulostaa O n neliö toiminnan. Tarkasteltaessa meidän pseudokoodilla, meillä on myös silmukka sisäkkäin toinen silmukka, joka todellakin kuulostaa O n squared toimintaa. Muista kuitenkin, että emme tarvitse etsiä yli koko lista määritettäessä minimi lajittelemattoman elementti? Kun tiesimme, että 4 oli lajiteltu Esimerkiksi emme täytyy katsoa sitä uudelleen. Joten tämä pienempi käyntiaika? Meidän luettelo pituus 6 tarvitsimme tehdä viisi vertailuja ensimmäisen elementin, neljä vertailuja toinen elementti, ja niin edelleen. Tämä tarkoittaa sitä, että vaiheiden kokonaismäärä on summa kokonaisluvut 1 listan pituus miinus 1. Voimme edustaa tämän kanssa summattu. Emme aio mennä summaussarjojen tänne. Mutta se osoittautuu, että tämä summattu on yhtä kuin n kertaa n miinus 1 yli 2. Tai vastaavasti, n potenssiin yli 2 miinus n. yli 2. Kun puhutaan asymptoottinen runtime, tämä n potenssiin termi tulee hallitsemaan tätä n. aikavälillä. Joten valinta tavallaan on O n neliö. Muistutan, että meidän esimerkissä valinta lajitella tarvitaan edelleen tarkista onko numero, joka on jo järjestetty tarpeen siirtää. Joten se tarkoittaa, että jos me juoksi valinta Lajittele yli jo järjestetty luettelo, se vaatisi sama määrä vaiheita kuin se olisi ajettaessa täysin lajittelemattoman luettelosta. Joten valinta sort on parhaassa tapauksessa suorituskyvyn n potenssiin, jota edustavat Omega n neliö. Ja se on siinä valinnassa tavallaan. Vain yksi monista algoritmien voimme järjestellä luettelon. Nimeni on Tommy, ja tämä on cs50.