- Comparate
- Cea mai mică până acum
- Interschimbate
- La locul lor
Sortarea prin selecție
Sortarea prin selecție construiește lista sortată de la început. Fiecare trecere parcurge valorile încă nesortate, o reține pe cea mai mică și o mută prin interschimbare pe prima poziție nesortată. Redați sortarea la orice viteză sau parcurgeți-o câte o comparație și urmăriți contoarele pentru comparații, interschimbări și treceri. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Casetele numără comparațiile, interschimbările și trecerile. Alegeți câte bare sunt, cum încep sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți câte bare sunt și cum încep: aleatoriu, aproape sortate, inversate sau cu puține valori distincte. Sau introduceți propriile numere.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
- Urmăriți cum se schimbă cea mai mică valoare de până acum pe măsură ce avansează căutarea și interschimbarea care o pune la locul ei la sfârșitul fiecărei treceri.
Cum funcționează sortarea prin selecție
Parcurgeți fiecare valoare din listă și rețineți-o pe cea mai mică. Interschimbați-o cu prima valoare: prima poziție este acum finală. Apoi faceți la fel cu restul listei, începând cu o poziție mai departe. După n − 1 treceri, fiecare valoare e la locul ei, iar ultima ajunge acolo de la sine.
Multe comparații, puține interschimbări
Căutarea nu se oprește niciodată mai devreme, pentru că doar după ce a verificat fiecare valoare rămasă poate fi sigură care e cea mai mică. Așa că sortarea prin selecție face exact n(n − 1)/2 comparații pentru n valori, fie că lista e sortată, inversată sau aleatorie. În schimb, face cel mult n − 1 interschimbări, una pe trecere. De aceea e o alegere bună când mutarea unei valori costă mult mai mult decât compararea a două.
Întrebări frecvente
Cum funcționează sortarea prin selecție?
Selectează în mod repetat cea mai mică valoare încă nesortată și o mută prin interschimbare pe prima poziție nesortată. După trecerea k, primele k poziții conțin cele mai mici k valori, în ordine.
Câte comparații și interschimbări face sortarea prin selecție?
Mereu n(n − 1)/2 comparații pentru n valori: 45 pentru 10 valori, 780 pentru 40. Numărul de interschimbări este cel mult n − 1, una pe trecere, și mai mic când cea mai mică valoare e deja la locul ei.
De ce durează o listă sortată la fel de mult ca una inversată?
Pentru că fiecare trecere trebuie să verifice fiecare valoare rămasă ca să fie sigură că a găsit-o pe cea mai mică. Spre deosebire de metoda bulelor și de sortarea prin inserție, sortarea prin selecție nu își poate da seama din comparații că lista e deja sortată.
Este sortarea prin selecție stabilă?
Nu în forma obișnuită. O interschimbare poate muta o valoare peste una egală: în 2, 2, 1, primul 2 se interschimbă cu 1 și ajunge după al doilea 2. O variantă care deplasează valorile în loc să le interschimbe este stabilă, cu prețul mai multor mutări.
Sunt trimise undeva numerele mele?
Nu. Sortarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor