Ce este Sortarea selecției?
SELECTION SORT este un algoritm de sortare a comparației care este utilizat pentru a sorta o listă aleatorie de articole în ordine crescătoare. Comparația nu necesită mult spațiu suplimentar. Necesită doar un spațiu de memorie suplimentar pentru variabila temporală.
Acest lucru este cunoscut sub numele de sortare în loc . Sortarea selecției are o complexitate de timp O (n 2 ) unde n este numărul total de articole din listă. Complexitatea timpului măsoară numărul de iterații necesare pentru sortarea listei. Lista este împărțită în două partiții: Prima listă conține elemente sortate, în timp ce a doua listă conține elemente nesortate.
În mod implicit, lista sortată este goală, iar lista nesortată conține toate elementele. Lista nesortată este apoi scanată pentru valoarea minimă, care este apoi plasată în lista sortată. Acest proces se repetă până când toate valorile au fost comparate și sortate.
În acest tutorial Algoritm, veți învăța:
- Ce este Sortarea selecției?
- Cum funcționează sortarea selecției?
- Definirea problemei
- Soluție (algoritm)
- Reprezentare vizuala
- Selecție Sortare program folosind Python 3
- Explicarea codului
- Complexitatea timpului de sortare a selecției
- Când se folosește sortarea de selecție?
- Avantajele sortării selecției
- Dezavantaje ale sortării selecției
Cum funcționează sortarea selecției?
Primul element din partiția nesortată este comparat cu toate valorile din partea dreaptă pentru a verifica dacă este valoarea minimă. Dacă nu este valoarea minimă, atunci poziția sa este schimbată cu valoarea minimă.
Exemplu:
- De exemplu, dacă indicele valorii minime este 3, atunci valoarea elementului cu indexul 3 este plasată la indexul 0 în timp ce valoarea care a fost la indexul 0 este plasată la indexul 3. Dacă primul element din partiția nesortată este valoarea minimă, apoi își returnează pozițiile.
- Elementul care a fost determinat ca valoare minimă este apoi mutat în partiția din partea stângă, care este lista sortată.
- Partea partiționată are acum un element, în timp ce partea nepartitionată are (n - 1) elemente în care n este numărul total de elemente din listă. Acest proces se repetă mereu până când toate articolele au fost comparate și sortate pe baza valorilor lor.
Definirea problemei
O listă de elemente care sunt în ordine aleatorie trebuie să fie sortată în ordine crescătoare. Luați în considerare următoarea listă ca exemplu.
[21,6,9,33,3]
Lista de mai sus ar trebui să fie sortată pentru a produce următoarele rezultate
[3,6,9,21,33]
Soluție (algoritm)
Pasul 1) Obțineți valoarea lui n care este dimensiunea totală a matricei
Pasul 2) Împărțiți lista în secțiuni sortate și nesortate. Secțiunea sortată este inițial goală, în timp ce secțiunea nesortată conține întreaga listă
Pasul 3) Alegeți valoarea minimă din secțiunea nepartitionată și plasați-o în secțiunea sortată.
Pasul 4) Repetați procesul (n - 1) ori până când toate elementele din listă au fost sortate.
Reprezentare vizuala
Având în vedere o listă de cinci elemente, următoarele imagini ilustrează modul în care algoritmul de sortare a selecției repetă valorile atunci când le sortați.
Următoarea imagine arată lista nesortată
Pasul 1)
Prima valoare 21 este comparată cu restul valorilor pentru a verifica dacă este valoarea minimă.
3 este valoarea minimă, deci pozițiile 21 și 3 sunt schimbate. Valorile cu fundal verde reprezintă partiția sortată a listei.
Pasul 2)
Valoarea 6 care este primul element din partiția nesortată este comparată cu restul valorilor pentru a afla dacă există o valoare mai mică
Valoarea 6 este valoarea minimă, deci își menține poziția.
Pasul 3)
Primul element al listei nesortate cu valoarea 9 este comparat cu restul valorilor pentru a verifica dacă este valoarea minimă.
Valoarea 9 este valoarea minimă, deci își menține poziția în partiția sortată.
Pasul 4)
Valoarea 33 este comparată cu restul valorilor.
Valoarea 21 este mai mică decât 33, deci pozițiile sunt schimbate pentru a produce lista nouă de mai sus.
Pasul 5)
Mai avem o singură valoare în lista nepartizionată. Prin urmare, este deja sortat.
Lista finală este ca cea afișată în imaginea de mai sus.
Selecție Sortare program folosind Python 3
Următorul cod arată implementarea sortării selecției folosind Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Rulați codul de mai sus produce următoarele rezultate
[3, 6, 9, 21, 33]
Explicarea codului
Explicația pentru cod este următoarea
Iată explicația Codului:
- Definește o funcție numită selectionSort
- Obține numărul total de elemente din listă. Avem nevoie de acest lucru pentru a determina numărul de treceri care trebuie făcute la compararea valorilor.
- Bucla exterioară. Folosește bucla pentru a itera prin valorile listei. Numărul de iterații este (n - 1). Valoarea lui n este 5, deci (5 - 1) ne dă 4. Aceasta înseamnă că iterațiile externe vor fi efectuate de 4 ori. În fiecare iterație, valoarea variabilei i este atribuită variabilei minValueIndex
- Buclă interioară. Folosește bucla pentru a compara cea mai stângă valoare cu celelalte valori din partea dreaptă. Cu toate acestea, valoarea pentru j nu începe de la indexul 0. Începe de la (i + 1). Aceasta exclude valorile care au fost deja sortate, astfel încât să ne concentrăm asupra elementelor care nu au fost încă sortate.
- Găsește valoarea minimă din lista nesortată și o plasează în poziția corectă
- Actualizează valoarea minValueIndex atunci când condiția de schimb este adevărată
- Compară valorile numerelor index minValueIndex și i pentru a vedea dacă acestea nu sunt egale
- Valoarea din stânga este stocată într-o variabilă temporală
- Valoarea inferioară din partea dreaptă ocupă prima poziție
- Valoarea care a fost stocată în valoarea temporală este stocată în poziția care a fost deținută anterior de valoarea minimă
- Returnează lista sortată ca rezultat al funcției
- Creează o listă el care are numere aleatorii
- Imprimați lista sortată după ce ați apelat funcția de sortare de selecție trecând în el ca parametru.
Complexitatea timpului de sortare a selecției
Complexitatea sortării este utilizată pentru a exprima numărul de timpi de execuție necesari pentru a sorta lista. Implementarea are două bucle.
Bucla exterioară care alege valorile una câte una din listă este executată de n ori, unde n este numărul total de valori din listă.
Bucla interioară, care compară valoarea din bucla exterioară cu restul valorilor, se execută de asemenea de n ori în care n este numărul total de elemente din listă.
Prin urmare, numărul execuțiilor este (n * n), care poate fi exprimat și ca O (n 2 ).
Sortarea selecției are trei categorii de complexitate și anume;
- Cel mai rău caz - aici lista furnizată este în ordine descrescătoare. Algoritmul efectuează numărul maxim de execuții care este exprimat ca [Big-O] O (n 2 )
- Cel mai bun caz - apare atunci când lista furnizată este deja sortată. Algoritmul efectuează numărul minim de execuții care este exprimat ca [Big-Omega] Ω (n 2 )
- Caz mediu - apare atunci când lista este în ordine aleatorie. Complexitatea medie este exprimată ca [Big-theta] ⊝ (n 2 )
Sortarea selecției are o complexitate spațială de O (1), deoarece necesită o variabilă temporală utilizată pentru schimbarea valorilor.
Când se folosește sortarea de selecție?
Sortarea selecției este cel mai bine utilizată atunci când doriți:
- Trebuie să sortați o mică listă de articole în ordine crescătoare
- Când costul valorilor de schimb este nesemnificativ
- Se folosește și atunci când trebuie să vă asigurați că toate valorile din listă au fost verificate.
Avantajele sortării selecției
Următoarele sunt avantajele tipului de selecție
- Se comportă foarte bine pe liste mici
- Este un algoritm în loc. Nu necesită mult spațiu pentru sortare. Pentru menținerea variabilei temporale este necesar un singur spațiu suplimentar.
- Se comportă bine la elementele care au fost deja sortate.
Dezavantaje ale sortării selecției
Următoarele sunt dezavantajele tipului de selecție.
- Are performanțe slabe atunci când lucrezi pe liste uriașe.
- Numărul de iterații efectuate în timpul sortării este n-pătrat, unde n este numărul total de elemente din listă.
- Alți algoritmi, cum ar fi quicksort, au performanțe mai bune în comparație cu tipul de selecție.
Rezumat:
- Sortarea selecției este un algoritm de comparație la fața locului, care este utilizat pentru a sorta o listă aleatorie într-o listă ordonată. Are o complexitate temporală de O (n 2 )
- Lista este împărțită în două secțiuni, sortate și nesortate. Valoarea minimă este selectată din secțiunea nesortată și plasată în secțiunea sortată.
- Acest lucru se repetă până când toate articolele au fost sortate.
- Implementarea pseudocodului în Python 3 implică utilizarea a două pentru bucle și dacă instrucțiunile pentru a verifica dacă este necesară schimbarea
- Complexitatea timpului măsoară numărul de pași necesari pentru sortarea listei.
- Cea mai rea situație de timp se întâmplă atunci când lista este în ordine descrescătoare. Are o complexitate temporală de [Big-O] O (n 2 )
- Cea mai bună situație de timp se întâmplă atunci când lista este deja în ordine crescătoare. Are o complexitate de timp de [Big-Omega] Ω (n 2 )
- Complexitatea timpului mediu al cazului se întâmplă atunci când lista este în ordine aleatorie. Are o complexitate temporală de [Big-theta] ⊝ (n 2 )
- Sortarea selecției este cel mai bine utilizată atunci când aveți o listă mică de articole de sortat, costul schimbului de valori nu contează și verificarea tuturor valorilor este obligatorie.
- Sortarea selecției nu funcționează bine pe liste uriașe
- Alți algoritmi de sortare, cum ar fi rapidul rapid, au performanțe mai bune în comparație cu sortarea de selecție.