If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Biblioteca de informatică

Curs: Biblioteca de informatică > Unitatea 1

Lecția 4: Sortarea prin selecție
Calculatoare
Biblioteca de informatică
Bazele informaticii
Sortarea prin selecție
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie

Analiza sortării prin selecție

Clasa Google
Sortarea prin selecție parcurge în mod repetat indicii vectorului, iar pentru fiecare indice apelează indexOfMinimum și swap. Dacă lungimea vectorului este n, atunci sunt n indici în vector.
Deoarece la fiecare execuție a structurii repetitive sunt rulate două instrucțiuni, ai putea crede că sortarea prin selecție rulează în total 2n instrucțiuni. Acest lucru nu este adevărat, pentru că indexOfMinimum și swap sunt de fapt funcții care au, la rândul lor, alte instrucțiuni care se execută la apel.
Câte instrucțiuni sunt executate la un singur apel al funcției swap? În general trei, deci fiecare apel swap are timp de execuție constant.
Câte instrucțiuni sunt executate la un singur apel al funcției indexOfMinimum? Trebuie să luăm în considerare și repetiția din indexOfMinimum. De câte ori se execută aceasta la un apel indexOfMinimum? Depinde de dimensiunea subșirului peste care iterează. Dacă subșirul este chiar vectorul (așa cum se întâmplă la primul pas), repetiția are loc de n ori, iar dacă subșirul este de lungime 6, repetiția are loc de 6 ori.
De exemplu, să spunem că vectorul este de lungime 8 și să ne gândim la modul în care operează sortarea prin selecție.
  1. La primul apel indexOfMinimum, algoritmul verifică toate valorile din vector, deci repetiția din indexOfMinimum se execută de 8 ori.
  2. La al doilea apel indexOfMinimum, verifică valorile din subșirul cu indici de la 1 la 7, deci repetiția din indexOfMinimum se execută de 7 ori.
  3. La al treilea apel, verifică subșirul cu indici de la 2 la 7; repetiția se execută de 6 ori.
  4. La al patrulea apel, verifică subșirul cu indici de la 3 la 7; repetiția se execută de 5 ori.
  5. ...
  6. La al optulea apel și cel final al funcției indexOfMinimum, repetiția se execută o singură dată.
Dacă însumăm numărul de execuții ale structurii repetitive din indexOfMinimum, obținem 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 execuții.

Paranteză: Calcularea sumelor de la 1 la n

Cum calculezi rapid suma 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1? Iată un truc. Haide să schimbăm ordinea în care adunăm numerele. Întâi adunăm 8 + 1, cea mai mare și cea mai mică valoare, și obținem 9. Apoi adunăm 7 + 2, a doua cea mai mare și a doua cea mai mică valoare, și obținem tot 9. Dar dacă adunăm 6 + 3? Tot 9. În final adunăm 5 + 4, tot 9. Deci ce obținem?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=4⋅9=36 .
Sunt patru perechi de numere, fiecare având suma 9. Iată deci metoda generală pentru a aduna orice șir de numere întregi consecutive:
  1. Adună cel mai mic și cel mai mare număr.
  2. Înmulțește suma respectivă cu numărul de perechi.
Dar dacă șirul are lungime impară și nu poți asocia toate numerele două câte două? Pur și simplu privește numărul din mijloc, cel fără pereche, ca fiind jumătate de pereche. De exemplu, haide să adunăm 1 + 2 + 3 + 4 + 5. Avem două perechi întregi (1 + 5 și 2 + 4, fiecare având suma 6) și o jumătate de pereche (3, care este jumătatea lui 6), reprezentând în total 2.5 perechi. Înmulțim 2.5⋅6=15 și obținem răspunsul corect.
Dar dacă numerele pe care le adunăm sunt de la 1 la n? Numim acest șir o progresie aritmetică. Suma celui mai mic și celui mai mare număr este n+1. Deoarece sunt în total n numere, există n/2 perechi (indiferent de paritatea lui n). Așadar, suma numerelor de la 1 la n este (n+1)(n/2), adică n2/2+n/2. Încearcă să aplici această formulă pentru n=5 și n=8.

Analiza asimptotică a timpului de execuție pentru sortarea prin selecție

Timpul total de execuție pentru sortarea prin selecție are trei componente:
  1. Timpul de execuție pentru toate apelurile către indexOfMinimum.
  2. Timpul de execuție pentru toate apelurile către swap.
  3. Timpul de execuție pentru restul repetiției din funcția selectionSort.
A doua și a treia componentă sunt ușor de calculat. Știm că se fac n apeluri către swap și fiecare apel are timp de execuție constant. Folosindu-ne de notația asimptotică, constatăm că timpul de execuție al tuturor apelurilor swap este Θ(n). Celelalte instrucțiuni din structura repetitivă din selectionSort verifică și incrementează variabila repetiței și apelează indexOfMinimum și swap. Aceste operații au tot timp de execuție constant și se repetă de n ori, rezultând din nou timpul de execuție Θ(n).
Pentru prima componentă (timpul de execuție pentru toate apelurile către indexOfMinimum) am calculat deja partea dificilă. Fiecare parcurgere a repetiției din indexOfMinimum are timp constant de execuție. Numărul de iterații ale repetiției este n la primul apel, apoi n−1, apoi n−2 și așa mai departe. Am văzut că această sumă, 1+2+⋯+(n−1)+n este o progresie aritmetică al cărei rezultat este (n+1)(n/2), sau n2/2+n/2. Așadar, timpul total pentru toate apelurile către indexOfMinimum este n2/2+n/2, de un număr constant de ori. Atunci când folosim notația Θ, nu luăm în considerare nici constantele, nici factorul 1/2 al termenului de ordin mai mic, deci timpul de execuție pentru toate apelurile către indexOfMinimum este Θ(n2).
Adunând timpii de execuție pentru cele trei componente, obținem Θ(n2) pentru apelurile către indexOfMinimum, Θ(n) pentru apelurile către swap și Θ(n) pentru restul repetiției din selectionSort. Θ(n2) este termenul dominant, deci putem afirma că timpul de execuție al sortării prin selecție este Θ(n2).
De asemenea, trebuie să observi că niciun caz nu este favorabil sau nefavorabil pentru sortarea prin selecție. Repetiția din indexOfMinimum va face mereu n2/2+n/2 iterații, indiferent de datele de intrare. Prin urmare, putem spune că sortarea prin selecție are timpul de execuție Θ(n2) în toate cazurile.
Haide să vedem cum Θ(n2) influențează în realitate timpul de execuție. Să presupunem că sortarea prin selecție sortează n valori în aproximativ n2/106 secunde. Inițial vom alege o valoare mai mică pentru n, de exemplu n=100. Asta înseamnă că timpul de execuție al sortării prin selecție este de aproximativ 1002/106=1/100 secunde, ceea ce pare destul de puțin. Dar dacă n=1000? Atunci sortarea prin selecție ar dura aproximativ 10002/106=1 secundă. Dimensiunea vectorului a crescut de 10 ori, dar timpul de execuție a crescut de 100 de ori. Dacă n=1,000,000? Atunci sortarea prin selecție ar dura 1,000,0002/106=1,000,000 secunde, adică puțin mai mult 11.5 zile. Creșterea dimensiunii vectorului de 1000 de ori ar crește timpul de execuție de un milion de ori!
Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.

Vrei să te alături conversației?

Conectare
Nici o postare încă.
Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.