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