[Powered by Google Translate] TOMMY: Să aruncăm o privire la fel de selecție, un algoritm pentru a lua o listă de numere și sortarea lor. Un algoritm, amintiți-vă, este pur și simplu un pas-cu-pas Procedura pentru realizarea unei sarcini. Ideea de bază din spatele fel de selecție este de a diviza Lista noastră în două părți - o parte sortati si o parte nesortate. La fiecare pas al algoritmului, un numar este mutat de la porțiunea nesortate la porțiunea sortate până în cele din urmă întreaga listă este sortată. Deci, aici este o listă de șase numere - 23, 42, 4, 16, 8, și 15. Chiar acum întreaga listă este considerat nesortate. Chiar dacă un număr ca 16 pot fi deja în corect sa Locul de amplasare, algoritmul nostru nu are nici o modalitate de a ști că, până la întreaga listă este sortată. Deci, vom lua în considerare fiecare număr să fie sortate până când vom rezolva o noi înșine. Știm că vrem lista să fie în ordine crescătoare. Deci, vom dori să construiască partea de sortat lista noastră de de la stânga la dreapta, mai mic la cel mai mare. Pentru a face acest lucru, vom avea nevoie pentru a găsi elementul minim nesortate și pune-l la sfârșitul porțiunii sortate. Deoarece această listă nu este sortată, singura modalitate de a face asta este de a uita-te la fiecare element în parte nesortate, amintindu- care element este mai mic și compararea fiecare element de asta. Deci, ne vom uita mai intai la 23. Acesta este primul element care le-am văzut, așa că vom aminti ca minim. Apoi, vom uita la 42. 42 este mai mare decât 23, deci 23 este încă minimă. Următorul este 4, care este mai mică de 23, deci vom aminti 4 ca minim. Următorul este 16, care este mai mare de 4, deci 4 este încă minimă. 8 este mai mare de 4, iar 15 este mai mare de 4, deci 4 trebuie să fie cel mai mic element de nesortate. Deci, chiar dacă, ca oameni, putem vedea imediat că 4 este elementul minim, algoritmul nostru are nevoie să se uite la fiecare element nesortate, chiar și după ce am gasit 4 - minim element. Deci, acum că ne-am găsit elementul minim, 4, vom dori pentru ao muta în partea de sortat lista. Deoarece acesta este primul pas, aceasta înseamnă că doriți să puneți 4 la începutul listei. Chiar acum 23 este de la inceputul listei, astfel încât hai sa schimb 4 și 23. Deci, acum, lista noastră de arată așa. Știm că 4 trebuie să fie în poziția sa finală, pentru că este atât mai mic element și elementul de la început a listei. Deci asta înseamnă că nu avem nevoie niciodată să-l mute din nou. Așa că hai să repetați acest proces pentru a adăuga un alt element la parte din lista de sortat. Noi știm că nu avem nevoie să se uite la 4, pentru că este deja sortate. Deci, putem incepe de la 42, pe care ne vom aminti ca minim element. Deci, data viitoare ne vom uita la 23, care este mai mică de 42, așa că am amintesc 23 este minim. În continuare vom vedea 16, care este mai puțin de 23, așa 16 este minim. Acum ne uităm la 8, care este mai mică de 16, așa 8 este minim. Și, în cele din urmă 8 este mai mic de 15, așa că știm că 8 este un minim nesortate element. Deci asta înseamnă că ar trebui să adauge la 8 la sortat porțiune din listă. Acum 4 este singurul element sortate, astfel încât dorim să plaseze următor 8 la 4. Deoarece 42 este primul element din partea nesortata a listă, vom dori să facă schimb de 42 și 8. Deci, acum, lista noastră de arată așa. 4 și 8 reprezintă porțiunea sortate din listă și Numerele rămase reprezintă nesortate porțiune din listă. Așa că să continuăm cu o altă iterație. Vom începe cu 23 de data asta, din moment ce nu trebuie să se uite la 4 și 8 mai, deoarece le-am fost deja sortate. 16 este mai puțin de 23, deci vom aminti 16 ca minim. 16 este mai mică de 42, dar 15 este mai mică de 16, deci 15 trebuie să fie elementul minim nesortate. Deci, acum vrem să schimb 15 și 23 la să ne dea această listă. Partea sortate a listei este format din 4, 8 și 15, precum și aceste elemente sunt încă nesortate. Dar doar așa se întâmplă că elementul următor nesortate, 16, este deja sortat. Cu toate acestea, nu există nici o cale pentru algoritmul nostru să știe că 16 este deja în locația corectă, așa că încă mai trebuie să repetați exact același proces. Deci, vedem că 16 este mai mică de 42, iar 16 este mai puțin de 23, așa 16 trebuie să fie elementul minim. Este imposibil de a schimba acest element cu el însuși, astfel încât să putem pur și simplu lăsați-l în această locație. Deci, avem nevoie de pașaport una mai mult a algoritmului nostru. 42 este mai mare de 23, deci 23 trebuie să fie minim nesortate element. După ce vom schimba 23 și 42, vom ajunge cu finala nostru sortate lista - 4, 8, 15, 16, 23, 42. Stim 42 trebuie să fie în locul corect, deoarece este singurul element rămas, și asta e un fel de selecție. Să formalizeze acum algoritmul nostru, cu unele pseudocod. Pe linia unu, putem vedea că avem nevoie pentru a integra peste fiecare element al listei. Cu excepția ultimul element, deoarece elementul 1 Lista este deja sortat. Pe linia doi, considerăm primul element al nesortate parte din lista pentru a fi minim, așa cum am procedat cu de exemplu, deci avem ceva pentru a compara cu. Linia trei începe o buclă al doilea în care am itera peste fiecare element de nesortate. Știm că după ce am iterații, sortate porțiunea din lista noastră trebuie să aibă elemente i în ea, deoarece fiecare pas sortează un element. Deci, primul element nesortate trebuie să fie în poziția I, plus 1. Pe linia patru, vom compara elementul curent la minim Elementul pe care le-am văzut până acum. Dacă elementul curent este mai mic decât minimul element, apoi ne amintim elementul curent ca noua minim pe linia cinci. În cele din urmă, pe liniile șase și șapte, am schimba minim element cu element nesortate în primul rând, astfel adăugându-l la partea de sortat lista. Odată ce avem un algoritm, o întrebare importantă de a cere noi înșine ca programatori este cât de mult a dura asta? Vom întreba mai întâi întrebarea cât timp durează pentru acest algoritm pentru a rula în cel mai rău caz? Amintesc să ne reprezentăm această funcționare timp cu notația O mare. În scopul de a determina elementul minim nesortate, am în esență, a trebuit să compare fiecare element în listă pentru a orice alt element din listă. Intuitiv, acest lucru sună ca o operațiune de O, N pătrat. Privind la pseudocod nostru, avem, de asemenea, o buclă imbricată în interiorul o altă buclă, care într-adevăr sună ca un O de funcționare pătrat nr. Cu toate acestea, amintiți-vă că nu am nevoie să se uite peste listă întreagă atunci când se determină elementul minim nesortate? Odată ce am știut că 4 a fost sortate, de exemplu, nu am făcut-o trebuie să se uite la el din nou. Deci, face acest lucru mai mic timpul de execuție? Pentru lista noastră de lungime 6, avem nevoie pentru a face cinci comparații pentru primul element, patru comparații pentru al doilea element, și așa mai departe. Asta înseamnă că numărul total de pași este suma de de numere întregi de la 1 la lungimea listei minus 1. Ne putem reprezenta acest lucru cu o însumare. Nu vom intra în somații aici. Dar se pare că acest însumării este egală cu de n ori n minus 1 peste 2. Sau echivalent, n pătrat de peste 2 minus n. peste 2. Atunci când vorbim despre timpul rulării asimptotică, acest termen n pătrat este de gând să domine acest termen nr. Deci, un fel de selecție este O de n pătrat. Reamintim că, în exemplul nostru, un fel de selecție încă necesare pentru a verifica dacă un număr care a fost deja sortate necesare pentru a fi mutate. Asta înseamnă că, dacă am alergat un fel de selecție peste o deja sortate listă, ar fi nevoie de același număr de pași în care ar fi atunci când rulează pe o listă complet nesortate. Deci, un fel de selecție are o performanță mai bun caz de pătrat N, pe care le reprezintă cu omega n pătrat. Și asta e tot un fel de selecție. Doar unul din algoritmii de mai multe, putem utilizați pentru a sorta o listă. Numele meu este Tommy, iar acest lucru este CS50.