[Musiikkia] DOUG Lloyd: Valinta sort on algoritmi, joka, kuten arvata saattaa, lajittelee joukon elementtejä. Ja algoritmi Recall on askel-askeleelta sarja ohjeisto valmiiksi tehtävän. 

Valinnassa lajitella Perusidea on tämä, löytää pienin lajittelemattoman elementti ja lisätä sen loppuun lajitellun luettelon. Tehokkaasti Mitä tämä on rakentaa lajiteltu lista, yksi osa kerrallaan. Rikkomatta alas pseudokoodina voisimme todeta tämä algoritmi seuraavasti, toista tämä kunnes ei lajittelemattoman elementtejä edelleen. Hae seuraavien lajittelemattoman tiedot löytää pienimmän arvon, sitten vaihtaa pienimmän arvon kanssa ensimmäinen osa lajittelemattoman osan. 

Se voi auttaa visualisoida, joten katsotaanpa katsomaan tätä. Joten tämä, väitän, on lajittelemattomat array ja olen ilmoittanut ilmoittamalla, että kaikki Elementtien ovat värillisiä punainen, ne eivät ole vielä järjestetty. Tämä on koko lajittelematon osa array. 

Joten mennään läpi vaiheet valinta lajitella lajitella tähän array. Joten jälleen, aiomme toistaa kunnes ei lajittelemattoman elementtejä edelleen. Aiomme haku kautta tiedot löytää pienimmän arvon, ja sitten vaihtaa tämän arvon kanssa ensimmäinen osa lajittelemattoman osan. 

Juuri nyt, jälleen, koko array on lajittelemattomana osa. Kaikki punaiset elementit lajittelemattomia. Joten me etsiä ja löydämme pienimmän arvon. Aloitamme alussa, menemme loppuun, löydämme pienin arvo on, yksi. Niin, että on osa yksi. Ja sitten osa kaksi, vaihtaa että arvoa ensimmäinen osa lajittelemattoman osan, tai ensimmäinen punainen elementti. 

Tässä tapauksessa se olisi viisi, joten me vaihtaa yhdestä viiteen. Kun teemme tämän, voimme visuaalisesti nähdä, että olemme muutti pienin arvostettu elementti array, jotta alusta. Tehokkaasti lajittelu että elementti. 

Ja jotta voimme todellakin vahvistaa ja toteavat, että yksi, lajitellaan. Ja niin me osoittavat lajiteltu osa meidän array, värjäämällä se sininen. 

Nyt vain toista prosessi uudelleen. Me etsiä lajittelemattomat osa array löytää pienin alkio. Tässä tapauksessa se on kaksi. 

Me vaihtaa että ensimmäisen elementti lajittelemattoman osan. Tässä tapauksessa kaksi myös sattuu olemaan ensimmäinen osa lajittelemattoman osan. Joten me vaihtaa kaksi itsensä kanssa, joka oikeastaan ​​vain lähtee kaksi missä se on, ja se on järjestetty. Jatkuu, me etsiä löytää pienin alkio. Se on kolme. Me vaihtaa sen ensimmäisen elementti, joka on viisi. Ja nyt kolme lajitellaan. 

Me etsimme kautta uudelleen, ja me löytää pienin elementti on neljä. Me vaihtaa sen ensimmäinen osa lajittelematonta osittain, ja nyt neljä lajitellaan. 

Huomaamme, että viisi on pienin elementti. Me vaihtaa sen ensimmäisen elementti lajittelemattoman osan. Ja nyt viisi lajitellaan. 

Ja sitten lopuksi, meidän lajittelemattomat osa koostuu vain yksi elementti, joten me etsiä ja huomaamme, että kuusi on pienin, ja itse asiassa ainoa elementti. Ja sitten voimme todeta, että se on järjestetty. Ja nyt olemme siirtynyt meidän array olemasta täysin lajittelematta punainen, täysin lajiteltu sininen, käyttäen valinta lajitella. 

Niin mitä pahimmassa tapauksessa täällä? Hyvin ehdoton pahin tapauksessa, meidän on katsottava yli kaikki elementit array löytää pienin lajittelemattoman elementti, ja meidän on toistettava tämä prosessi n kertaa. Kerran kutakin alkiota koska me vain tässä algoritmi, lajitella yksi elementti kerrallaan. 

Mikä on parhaassa tapauksessa? No se on täsmälleen sama, eikö? Meillä on todellakin vielä selata jokainen alkio varmistaakseen, että se on, Itse asiassa, pienin elementti. 

Joten pahimmassa tapauksessa runtime, me joutua toistamaan prosessi n kertaa, kerran kutakin n elementtejä. Ja parhaassa tapauksessa, meidän täytyy tehdä samoin. 

Joten ajattelu takaisin meidän laskennallinen vaativuus työkalupakki, mitä luulet on pahin tapauksessa runtime valintaan lajitella? Mitä luulet on paras tapauksessa runtime valintaan lajitella? 

Arvasit Big O n potenssiin, ja Big Omega n potenssiin? Olisit oikeassa. Ne ovat itse asiassa, Pahimmassa tapauksessa ja parhaassa tapauksessa ajaa ajat, valinnan lajitella. 

Olen Doug Lloyd. Tämä on CS50.