Algoritmi în acțiune
Algoritmi în acțiune este o simulare interactivă gratuită din StudyFi Lab. Rulează direct în browser, fără înregistrare și fără instalare.
Sortare și căutare, pas cu pas
Experimente
Sortarea prin metoda bulelor
Sortarea prin metoda bulelor compară elemente vecine și le interschimbă dacă sunt în ordinea greșită. După fiecare parcurgere, cel mai mare element a „urcat” la final, așa că partea nesortată se scurtează. Dacă o parcurgere nu face nicio interschimbare, tabloul este sortat. În cel mai rău caz sunt necesare n(n−1)/2 comparații, adică O(n²).
Încearcă: Alege intrarea inversată și compară numărul de comparații cu n(n−1)/2. Apoi încearcă un tablou aproape sortat — se oprește după câteva parcurgeri.
Sortarea prin inserție
Sortarea prin inserție seamănă cu aranjarea cărților în mână: partea din stânga este deja sortată, iar fiecare element nou (key) se mută spre stânga până întâlnește unul mai mic. Pe drum, elementele mai mari se deplasează cu o poziție la dreapta. Pe date aleatoare este O(n²), dar pe date aproape sortate aproape O(n) — un tablou sortat are nevoie doar de n−1 comparații.
Încearcă: Rulează-l pe un tablou aproape sortat, apoi pe unul inversat. De câte ori mai multe deplasări are nevoie cel inversat?
Sortarea prin interclasare
Sortarea prin interclasare împarte tabloul în două jumătăți, sortează fiecare jumătate la fel (recursivitate) și apoi interclasează cele două jumătăți sortate: ia mereu cel mai mic dintre cele două elemente din față. Înjumătățirea dă log₂ n niveluri, iar fiecare nivel prelucrează toate cele n elemente, deci timpul este mereu O(n log n). La egalitate ia elementul din stânga, de aceea este stabilă.
Încearcă: Încearcă un tablou inversat și apoi unul aproape sortat, de aceeași mărime. Numărul de comparații abia se schimbă — ordinea datelor de intrare contează puțin.
Sortarea rapidă
Sortarea rapidă alege un pivot — aici ultimul element al secvenței (partiționarea Lomuto) — și rearanjează secvența astfel încât elementele mai mici să ajungă la stânga, iar restul la dreapta. Pivotul ajunge astfel pe locul lui final, iar cele două părți se sortează la fel. În medie este O(n log n), dar când pivotul împarte prost (de exemplu la un tablou deja sortat sau inversat) scade la O(n²).
Încearcă: Compară o intrare aleatoare cu una inversată. La tabloul inversat pivotul este mereu cel mai mare sau cel mai mic — urmărește cum sare numărul de comparații.
Căutare liniară vs. binară
Căutarea liniară verifică elementele unul câte unul, așa că în cel mai rău caz are nevoie de n pași — O(n). Căutarea binară funcționează doar pe un tablou sortat: se uită la mijloc și, în funcție de rezultat, elimină o jumătate întreagă. După fiecare pas rămâne cel mult jumătate, deci ajung cel mult ⌈log₂(n+1)⌉ pași — O(log n). Pentru 40 de elemente sunt 6 pași în loc de 40.
Încearcă: Setează 40 de elemente și caută ultima valoare. Apoi alege un număr care nu este în tablou — câți pași îi trebuie fiecărei căutări ca să afle asta?
Cursa algoritmilor de sortare
Toți cei patru algoritmi sortează aceeași intrare, iar pe fiecare culoar un pas înseamnă o comparație sau o mutare. Algoritmii O(n²) (bulelor și inserție) cresc cu mărimea tabloului mult mai repede decât cei O(n log n) (interclasare și rapidă). Ordinea depinde însă și de intrare: pe un tablou aproape sortat câștigă adesea sortarea prin inserție.
Încearcă: Pornește cursa pe un tablou aleator de 40 de elemente, apoi treci la aproape sortat. Se schimbă câștigătorul?
Întrebări frecvente
Ce este Algoritmi în acțiune?
Algoritmi în acțiune este o simulare interactivă gratuită din StudyFi Lab. Rulează direct în browser, fără înregistrare și fără instalare. Sortare și căutare, pas cu pas
Algoritmi în acțiune este gratuit?
Da. Algoritmi în acțiune este complet gratuit. Funcționează în browser pe calculator, tabletă și telefon și nu ai nevoie de cont.
Ce pot explora în Algoritmi în acțiune?
Sortarea prin metoda bulelor, Sortarea prin inserție, Sortarea prin interclasare, Sortarea rapidă, Căutare liniară vs. binară, Cursa algoritmilor de sortare.
Ce arată experimentul „Sortarea prin metoda bulelor”?
Sortarea prin metoda bulelor compară elemente vecine și le interschimbă dacă sunt în ordinea greșită. După fiecare parcurgere, cel mai mare element a „urcat” la final, așa că partea nesortată se scurtează. Dacă o parcurgere nu face nicio interschimbare, tabloul este sortat. În cel mai rău caz sunt necesare n(n−1)/2 comparații, adică O(n²).
Ce arată experimentul „Sortarea prin inserție”?
Sortarea prin inserție seamănă cu aranjarea cărților în mână: partea din stânga este deja sortată, iar fiecare element nou (key) se mută spre stânga până întâlnește unul mai mic. Pe drum, elementele mai mari se deplasează cu o poziție la dreapta. Pe date aleatoare este O(n²), dar pe date aproape sortate aproape O(n) — un tablou sortat are nevoie doar de n−1 comparații.
Înveți pentru un test?
Încarcă-ți notițele și StudyFi le transformă în flashcarduri, teste și podcasturi.