[MUSIC JOC] DOUG LLOYD: un fel de selecție este o algoritm care, așa cum s-ar putea aștepta, sortează un set de elemente. Și amintesc algoritm este un set de pas-cu-pas de instrucțiuni pentru finalizarea unei sarcini. 

În selecție sorta Ideea de bază este acest lucru, găsi cel mai mic element nesortat și adăugați-l la sfârșitul listei sortate. Efectiv ceea ce face acest lucru este construi o listă sortată, un element la un moment dat. Breaking-l în jos pentru a pseudocod am putea afirma acest algoritm după cum urmează, se repetă acest lucru până când nici un element nesortate rămân. Căutați prin nesortat date pentru a găsi cea mai mică valoare, apoi schimba valoarea cea mai mică, cu Primul element al părții nesortate. 

Aceasta poate ajuta pentru a vizualiza acest lucru, Să aruncăm o privire la acest lucru. Deci acest lucru, eu susțin, este o matrice nesortate și am indicat prin care indică faptul că toate din elementele sunt de culoare roșie, ele nu sunt sortate încă. Aceasta este întregul parte nesortate din matrice. 

Deci, hai sa mergem prin etapele de selecție fel pentru a sorta această matrice. Deci, din nou, vom repeta până rămâne nici un element nesortate. Vom căutare prin date pentru a găsi cea mai mică valoare, și apoi de swap că valoarea cu Primul element al părții nesortate. 

Chiar acum, din nou, întreaga matrice este partea nesortate. Toate elementele roșii sunt nesortate. Asa ca am căuta prin și găsim cea mai mică valoare. Începem de la început, mergem până la capăt, găsim cea mai mică valoare este, o. Deci asta e prima parte. Și apoi partea a doua, schimb ca valoarea cu primul element al părții nesortate, sau primul element roșie. 

În acest caz, care ar fi cinci, asa ca am schimba una și cinci. Când facem acest lucru, putem vezi vizual că am mutat de prim rang mai mic element de matrice, la foarte început. Sortare în mod eficient acest element. 

Și astfel încât să putem confirma, într-adevăr și de stat, care este de este sortată. Și așa vom indica porțiunea sortate de oferta noastră, prin colorarea aceasta albastru. 

Acum ne repeta doar procesul din nou. Cautam prin partea nesortate de matrice pentru a găsi cel mai mic element. În acest caz, este de două. 

Am schimba că, odată cu primul element al părții nesortate. În acest caz, de două, de asemenea, se întâmplă să fie primul element al părții nesortate. Așa că am două schimb cu ea însăși, care de fapt doar două frunze unde este, și este sortate. Continuând pe, căutăm prin pentru a găsi cel mai mic element. E trei. Am schimba cu primul Element, care este de cinci. Și acum trei sunt sortate. 

Am căuta prin nou, iar noi găsi cel mai mic element este de patru. Am schimba cu primul element al parte nesortate, iar acum patru sunt sortate. 

Constatăm că cinci este cel mai mic element. Am schimba cu primul element al părții nesortate. Și acum cinci sunt sortate. 

Și apoi în cele din urmă, ne parte nesortate constă de doar un singur element, asa ca am căuta prin și constatăm că șase este mai mic, și, de fapt, doar elementul. Și apoi putem afirma că este sortate. Și acum ne-am pornit oferta noastră de a fi complet nesortate în roșu, a sortate complet în albastru, folosind selecția fel. 

Deci, ce este cel mai rău caz aici? Ei bine, în cel mai rău absolut caz, trebuie să se uite peste toate elementele matricei la găsi cel mai mic element nesortat, și trebuie să repetăm acest proces de n ori. Odată pentru fiecare element al matricei pentru că numai noi, în acest algoritm, fel un element la momentul. 

Care este cel mai bun caz? Ei bine, e exact la fel, nu? Noi de fapt, au să-și intensifice în continuare prin fiecare singur element de matrice în scopul de a confirma faptul că este, în fapt, cel mai mic element. 

Deci cel mai rău Runtime caz, ne vom trebuie să repete un proces de n ori, o dată pentru fiecare dintre n elemente. Și în cel mai bun caz, trebuie să facă același lucru. 

Deci, gândire înapoi nostru set de instrumente de calcul complexitatea, ce crezi că este cel mai rău caz de execuție pentru selectarea fel? Care credeți că este cel mai bun caz de execuție pentru selectarea fel? 

Ai ghicit Big O N pătrat, și Big Omega de n pătrat? Ai avea dreptate. Acestea sunt, de fapt, cel mai rău caz și cel mai bun caz a alerga ori, pentru selectarea fel. 

Sunt Doug Lloyd. Acest lucru este CS50.