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