Sortare selecție este un algoritm simplu de sortare. Acest algoritm de sortare este un algoritm bazat pe Comparație în loc în care lista este împărțită în două părți, partea sortată la capătul din stânga și partea nesortată la capătul din dreapta. Inițial, partea sortată este goală, iar partea nesortată este întreaga listă.
cel mai mic element este selectat din matricea nesortată și schimbat cu elementul din stânga, iar acel element devine o parte a matricei sortate. Acest proces continuă să se miște limita matrice nesortate de un element la dreapta.
acest algoritm nu este potrivit pentru seturi mari de date, deoarece complexitatea sa medie și cea mai gravă sunt de la hectar(N2), unde n este numărul de itemi.
Cum Funcționează Sortarea Selecției?
luați în considerare următorul tablou descris ca exemplu.
pentru prima poziție din lista sortată, întreaga listă este scanată secvențial. Prima poziție în cazul în care 14 este stocat în prezent, vom căuta întreaga listă și pentru a găsi că 10 este cea mai mică valoare.
deci înlocuim 14 cu 10. După o iterație 10, care se întâmplă să fie valoarea minimă din listă, apare în prima poziție a listei sortate.
pentru a doua poziție, unde se află 33, începem să scanăm restul listei într-o manieră liniară.
constatăm că 14 este a doua cea mai mică valoare din listă și ar trebui să apară pe locul doi. Schimbăm aceste valori.
după două iterații, două valori minime sunt poziționate la început într-o manieră sortată.
același proces este aplicat la restul elementelor din matrice.
urmează o descriere picturală a întregului proces de sortare −
acum, să învățăm câteva aspecte de programare ale sortării selecției.
algoritm
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
pseudocod
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
pentru a afla despre implementarea sortării selecției în limbajul de programare C, faceți clic aici.