Sortare prin selecție

Găsește cea mai mică valoare rămasă și o aduce, printr-o schimbare, pe următoarea poziție. Face foarte puține schimbări, dar mereu același număr de comparații.

cel mai bun caz Ω(n²)
caz mediu Θ(n²)
cel mai rău caz O(n²)
memorie O(1)
instabil
fără memorie suplimentară

Ce înseamnă acești termeni?

Cel mai bun caz: cum crește timpul cu mărimea n a listei când intrarea e cea mai ușoară pentru acest algoritm.
Caz mediu: creșterea obișnuită a timpului. La n², de două ori mai multe valori cer cam de patru ori mai mult timp; n log n crește mai lent.
Cel mai rău caz: creșterea pe intrarea cea mai grea. Util când viteza nu are voie să scadă niciodată.
Memorie: câtă memorie suplimentară e necesară pe lângă listă. 1 înseamnă câteva variabile, n înseamnă o copie a listei.
Stabil: două valori egale își păstrează ordinea inițială. Contează când sortezi după un singur câmp al unei înregistrări.
Fără memorie suplimentară: sortează chiar în listă, fără o a doua listă.

comparare
mutare
minim curent
pe poziția finală

0 / 399 pași

Comparații Schimbări

Apasă pe redare: liniile arată cum crește costul în timpul sortării

Viteză 8 pași/s

Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.

Încearcă: Alege o listă inversată. Numărul de comparații rămâne exact același ca pentru orice altă listă.

Cum funcționează

Caută cea mai mică valoare în partea nesortată și o schimbă cu prima valoare nesortată. Așa, încă o valoare ajunge pe poziția ei finală. Verifică mereu toate valorile rămase, chiar dacă lista e deja sortată.

Când este o alegere bună

Util când mutarea datelor costă mult, dar citirea lor e ieftină, pentru că face cel mult o schimbare pe poziție. În majoritatea celorlalte cazuri, sortarea prin inserție e alegerea simplă mai bună.