Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 4: Sortarea prin selecție- Sortare
- Provocare: implementare swap
- Pseudocodul sortării prin selecție
- Provocare: Determinarea minimului într-un subvector
- Provocare: implementează sortarea prin selecție
- Analiza sortării prin selecție
- Proiect: vizualizare sortare prin selecție
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Analiza sortării prin selecție
Sortarea prin selecție parcurge în mod repetat indicii vectorului, iar pentru fiecare indice apelează , atunci sunt indici în vector.
indexOfMinimum
și swap
. Dacă lungimea vectorului este Deoarece la fiecare execuție a structurii repetitive sunt rulate două instrucțiuni, ai putea crede că sortarea prin selecție rulează în total 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 ori, iar dacă subșirul este de lungime 6, repetiția are loc de 6 ori.
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 De exemplu, să spunem că vectorul este de lungime 8 și să ne gândim la modul în care operează sortarea prin selecție.
- La primul apel
indexOfMinimum
, algoritmul verifică toate valorile din vector, deci repetiția dinindexOfMinimum
se execută de 8 ori. - La al doilea apel
indexOfMinimum
, verifică valorile din subșirul cu indici de la 1 la 7, deci repetiția dinindexOfMinimum
se execută de 7 ori. - La al treilea apel, verifică subșirul cu indici de la 2 la 7; repetiția se execută de 6 ori.
- La al patrulea apel, verifică subșirul cu indici de la 3 la 7; repetiția se execută de 5 ori.
- ...
- 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
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?
Sunt patru perechi de numere, fiecare având suma 9. Iată deci metoda generală pentru a aduna orice șir de numere întregi consecutive:
- Adună cel mai mic și cel mai mare număr.
- Î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 și obținem răspunsul corect.
Dar dacă numerele pe care le adunăm sunt de la 1 la ? Numim acest șir o progresie aritmetică. Suma celui mai mic și celui mai mare număr este . Deoarece sunt în total numere, există perechi (indiferent de paritatea lui ). Așadar, suma numerelor de la 1 la este , adică . Încearcă să aplici această formulă pentru și .
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:
- Timpul de execuție pentru toate apelurile către
indexOfMinimum
. - Timpul de execuție pentru toate apelurile către
swap
. - 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 apeluri către . Celelalte instrucțiuni din structura repetitivă din ori, rezultând din nou timpul de execuție .
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 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 Pentru prima componentă (timpul de execuție pentru toate apelurile către la primul apel, apoi , apoi și așa mai departe. Am văzut că această sumă, este o progresie aritmetică al cărei rezultat este , sau . Așadar, timpul total pentru toate apelurile către , 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
) 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 indexOfMinimum
este indexOfMinimum
este Adunând timpii de execuție pentru cele trei componente, obținem pentru apelurile către pentru apelurile către pentru restul repetiției din este termenul dominant, deci putem afirma că timpul de execuție al sortării prin selecție este .
indexOfMinimum
, swap
și selectionSort
. De asemenea, trebuie să observi că niciun caz nu este favorabil sau nefavorabil pentru sortarea prin selecție. Repetiția din iterații, indiferent de datele de intrare. Prin urmare, putem spune că sortarea prin selecție are timpul de execuție în toate cazurile.
indexOfMinimum
va face mereu Haide să vedem cum influențează în realitate timpul de execuție. Să presupunem că sortarea prin selecție sortează valori în aproximativ secunde. Inițial vom alege o valoare mai mică pentru , de exemplu . Asta înseamnă că timpul de execuție al sortării prin selecție este de aproximativ secunde, ceea ce pare destul de puțin. Dar dacă ? Atunci sortarea prin selecție ar dura aproximativ secundă. Dimensiunea vectorului a crescut de 10 ori, dar timpul de execuție a crescut de 100 de ori. Dacă ? Atunci sortarea prin selecție ar dura 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?
Nici o postare încă.