Pseudocodul sortării prin selecție

Există mai multe metode pentru a sorta cărțile. Iată una simplă, numită sortare prin selecție, pe care probabil ai folosit-o și tu când ai sortat cărțile mai devreme:

Acest algoritm se numește sortare prin selecție pentru că selectează în mod repetat următorul cel mai mic element și îl schimbă cu altul din șir pentru a-l aduce pe poziția corectă.

Poți vedea mai jos cum funcționează algoritmul. Apasă pe „Step” pentru a urmări algoritmul pas cu pas, apoi, după ce l-ai înțeles, apasă butonul „Play” pentru a vedea sortarea până la final.

Acum că ai văzut cum lucrează algoritmul, ce părere ai despre el? Care pas pare să dureze cel mai mult timp? Cum crezi că ar funcționa algoritmul pe vectori de dimensiuni mari? Ține minte aceste întrebări pe măsură ce parcurgi algoritmul și îl implementezi.

Unul dintre pașii sortării prin selecție este găsirea următoarei cele mai mici cărți ce trebuie adusă pe poziția corectă. De exemplu, dacă șirul (vectorul) are inițial valorile [13, 19, 18, 4, 10], întâi trebuie să aflăm pe ce poziție este cel mai mic element din șir. În cazul de față, 4 este cea mai mică valoare și se află pe poziția 3 (indexarea se face începând de la 0).

Sortarea prin selecție schimbă valoarea de pe poziția 3 cu valoarea de pe poziția 0, rezultând șirul [4, 19, 18, 13, 10]. Acum trebuie să găsim poziția celui de-al doilea cel mai mic element, pentru a-l schimba cu cel de pe poziția 1.

Ar fi complicat să scrii un program care găsește poziția celui de-al doilea minim din șir. O soluție mai bună ar fi să observi că cea mai mică valoare se află deja pe poziția 0, deci ai nevoie să găsești minimul din subșirul care începe de la poziția 1. Vom numi subșir o porțiune din șirul inițial. În exemplul de mai sus, dacă șirul este [4, 19, 18, 13, 10], atunci cea mai mică valoare din subșirul care începe de la poziția 1 este 10 și este pe poziția 4 în șirul inițial. Așadar, pe poziția 4 se află al doilea cel mai mic element din întregul șir.

Încearcă această strategie la următoarea provocare, iar apoi vei avea tot ce îți trebuie ca să implementezi algoritmul de selecție directă.

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.