Sortarea prin selecție

Sortarea prin selecție ordonează o listă așa cum mulți își aranjează cărțile de joc din mână: găsiți-o pe cea mai mică, puneți-o prima, apoi găsiți-o pe cea mai mică dintre celelalte. Face multe comparații, dar foarte puține interschimbări, iar timpul de rulare aproape nu depinde de ordinea listei.

Bare de înălțimi diferite în curs de sortare, cu partea sortată în stânga, cea mai mică bară rămasă evidențiată și o săgeată care arată interschimbarea ei pe poziția corectă
Bare de înălțimi diferite în curs de sortare, cu partea sortată în stânga, cea mai mică bară rămasă evidențiată și o săgeată care arată interschimbarea ei pe poziția corectă

Ideea

Împărțiți lista într-o parte sortată în stânga, goală la început, și o parte nesortată în dreapta. Parcurgeți partea nesortată și rețineți unde se află cea mai mică valoare. Interschimbați acea valoare cu prima valoare nesortată: partea sortată a crescut cu unu. Repetați până rămâne o singură valoare, care trebuie să fie cea mai mare.

Un exemplu

Luați 5, 1, 4, 2, 8. Prima trecere verifică toate cele cinci valori, găsește că 1 e cea mai mică și o interschimbă cu 5: 1, 5, 4, 2, 8. A doua trecere verifică 5, 4, 2, 8, găsește 2 și o interschimbă cu 5: 1, 2, 4, 5, 8. A treia trecere găsește 4 deja la locul ei, iar a patra găsește 5 deja la locul ei, deci nu se mută nimic. Rezultă 4 + 3 + 2 + 1 = 10 comparații și doar 2 interschimbări. Metoda bulelor are nevoie de 4 interschimbări pe aceeași listă.

Mereu același număr de comparații

Ca să fie sigură care valoare e cea mai mică, căutarea trebuie să verifice fiecare valoare rămasă. Trecerea 1 face n − 1 comparații, trecerea 2 face n − 2 și așa mai departe până la 1, adică n(n − 1)/2 în total. Acest număr nu depinde de listă: o listă sortată costă exact tot atâtea comparații cât una inversată. Sortarea prin selecție nu se poate opri mai devreme, pentru că o căutare care găsește cea mai mică valoare deja în față nu a aflat nimic despre rest.

Puține interschimbări

Fiecare trecere face cel mult o interschimbare, așa că sortarea prin selecție nu face niciodată mai mult de n − 1 interschimbări și o sare atunci când cea mai mică valoare e deja la locul ei. Metoda bulelor și sortarea prin inserție fac atâtea interschimbări câte perechi sunt în ordine greșită, adică până la aproximativ n²/2. Când scrierea unei valori e mult mai costisitoare decât citirea a două, de exemplu în memoria care se uzează la fiecare scriere, numărul mic de interschimbări este un avantaj.

Nu este stabilă

O sortare este stabilă când valorile egale își păstrează ordinea inițială. Sortarea prin selecție nu este, pentru că o interschimbare la distanță mare poate muta o valoare peste una egală. În 2, 2, 1, prima trecere interschimbă primul 2 cu 1, rezultând 1, 2, 2, cu cei doi de 2 acum în ordine inversă. O variantă care deplasează valorile intermediare în loc să interschimbe este stabilă, dar mută mult mai multe valori.

Explorați

Deschideți aplicația și apăsați Redare sau apăsați Pas ca să avansați câte o comparație. Valoarea verificată este evidențiată, cea mai mică valoare de până acum are culoarea ei, iar fiecare trecere se încheie cu o interschimbare în partea sortată din stânga. Încercați o listă sortată și una inversată: comparațiile ies la fel, doar interschimbările diferă.

Întrebări frecvente

Care este complexitatea în timp a sortării prin selecție?

O(n²) în orice caz: exact n(n − 1)/2 comparații pentru n valori, oricare ar fi ordinea lor. Face cel mult n − 1 interschimbări și are nevoie doar de O(1) memorie suplimentară.

Care e diferența dintre sortarea prin selecție și metoda bulelor?

Metoda bulelor interschimbă vecinii pe parcurs și se poate opri mai devreme când o trecere nu face interschimbări. Sortarea prin selecție doar reține unde e cea mai mică valoare și face o singură interschimbare la sfârșitul fiecărei treceri. Sortarea prin selecție face mai puține interschimbări; metoda bulelor e mai rapidă pe liste aproape sortate.

Este sortarea prin selecție stabilă?

Nu. O interschimbare poate muta o valoare peste alta egală cu ea, așa că valorile egale își pot schimba ordinea. Poate fi făcută stabilă deplasând valorile în loc să le interschimbe, ceea ce costă mai multe mutări.

Ce legătură are heapsort cu sortarea prin selecție?

Heapsort este o sortare prin selecție cu un mod mai rapid de a găsi următoarea valoare: păstrează partea nesortată într-un heap, așa că fiecare selecție durează aproximativ log n pași în loc de o parcurgere completă. Asta reduce totalul la O(n log n).

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați sortarea prin selecție