Sortare selecție: algoritm explicat cu Python Exemplu de cod

Ce este Selection Sort?

SELECTARE SORT este un algoritm de sortare prin comparație care este folosit 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ă.

Aceasta este cunoscută sub numele de la loc triere. Sortarea de selecție are o complexitate de timp de O(n²) 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 articole sortate, în timp ce a doua listă conține articole 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.

Cum funcționează sortarea de selecție?

Primul articol 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 indice 3 este plasată la indicele 0, în timp ce valoarea care era la indicele 0 este plasată la indicele 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 nepartiționată are (n – 1) elemente unde n este numărul total de elemente din listă. Acest proces se repetă din nou și din nou până când toate articolele au fost comparate și sortate pe baza valorilor lor.

Definiția problemei

O listă de elemente care sunt în ordine aleatorie trebuie sortată în ordine crescătoare. Luați în considerare următoarea listă ca exemplu.

[21,6,9,33,3]

Lista de mai sus trebuie sortată pentru a produce următoarele rezultate

[3,6,9,21,33]

Soluție (algoritm)

Pas 1) Obțineți valoarea lui n care este dimensiunea totală a matricei

Pas 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ă

Pas 3) Alegeți valoarea minimă din secțiunea nepartiționată și plasați-o în secțiunea sortată.

Pas 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 iterează prin valori atunci când le sortează.

Următoarea imagine arată lista nesortată

Pas 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.

Pas 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.

Pas 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ă.

Pas 4)

Valoarea 33 este comparată cu restul valorilor.

Valoarea 21 este mai mică decât 33, astfel încât pozițiile sunt schimbate pentru a produce noua listă de mai sus.

Pas 5)

Mai avem o singură valoare în lista nepartiționată. Prin urmare, este deja sortat.

Lista finală este ca cea prezentată în imaginea de mai sus.

Selectare 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 = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Rularea codului 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 atunci când comparăm valori.
Bucla exterioară. Utilizează 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 exterioare vor fi efectuate de 4 ori. În fiecare iterație, valoarea variabilei i este atribuită variabilei minValueIndex
Bucla interioară. Utilizează bucla pentru a compara valoarea din stânga cu celelalte valori din partea dreaptă. Cu toate acestea, valoarea pentru j nu începe de la indicele 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ă în 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 de index minValueIndex și i pentru a vedea dacă nu sunt egale
Valoarea cea mai 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
Tipăriți lista sortată după apelarea funcției de sortare a selecției trecând el ca parametru.

Timp Complexitatea selecției Sortare

Complexitatea sortării este utilizată pentru a exprima numărul de execuții necesare pentru sortarea listei. 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, este, de asemenea, executată de n ori, unde n este numărul total de elemente din listă.

Prin urmare, numărul de execuții este (n * n), care poate fi exprimat și ca O(n²).

Sortarea de selecție are trei categorii de complexitate și anume;

Cel mai rău caz – aici este lista furnizată în ordine descrescătoare. Algoritmul realizează numărul maxim de execuții care este exprimat ca [Big-O] O(n²)
Cel mai bun caz – acest lucru se întâmplă atunci când lista furnizată este deja sortată. Algoritmul realizează numărul minim de execuții care este exprimat ca [Big-Omega] ?(n²)
Caz mediu – acest lucru se întâmplă atunci când lista este în ordine aleatorie. Complexitatea medie este exprimată ca [Big-theta] ?(n²)

Sortarea de selecție are o complexitate spațială de O(1), deoarece necesită o variabilă temporală utilizată pentru schimbarea valorilor.

Când să utilizați sortarea de selecție?

Sortarea de selecție este utilizată cel mai bine atunci când doriți:

Trebuie să sortați o listă mică de articole în ordine crescătoare
Când costul schimbului de valori este nesemnificativ
Este folosit ș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 sortării de selecție

Funcționează foarte bine pe liste mici
Este un algoritm pe loc. Nu necesită mult spațiu pentru sortare. Este necesar doar un spațiu suplimentar pentru menținerea variabilei temporale.
Funcționează bine pe articolele care au fost deja sortate.

Dezavantajele sortării selecției

Următoarele sunt dezavantajele sortării de selecție.

Funcționează slab atunci când lucrează pe liste uriașe.
Numărul de iterații făcute în timpul sortării este n pătrat, unde n este numărul total de elemente din listă.
Alți algoritmi, cum ar fi sortarea rapidă, au performanțe mai bune în comparație cu sortarea prin selecție.

Rezumat

Sortarea selecției este un algoritm de comparație la locul lui care este utilizat pentru a sorta o listă aleatorie într-o listă ordonată. Are o complexitate temporală de O(n²)
Lista este împărțită în două secțiuni, sortate și nesortate. Valoarea minimă este aleasă din secțiunea nesortată și plasată în secțiunea sortată.
Acest lucru se repetă până când toate elementele au fost sortate.
Implementarea pseudocodului în Python 3 implică utilizarea a două bucle for și instrucțiuni if pentru a verifica dacă este necesară schimbarea
Complexitatea timpului măsoară numărul de pași necesari pentru sortarea listei.
Cel mai rău caz de complexitate se întâmplă atunci când lista este în ordine descrescătoare. Are o complexitate temporală de [Big-O] O(n²)
Cel mai bun caz, complexitatea timpului apare atunci când lista este deja în ordine crescătoare. Are o complexitate temporală de [Big-Omega]?(n²)
Complexitatea timpului mediu de caz apare atunci când lista este în ordine aleatorie. Are o complexitate temporală de [Big-theta]? (n²)
Sortarea prin selecție este utilizată cel mai bine 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 de selecție nu funcționează bine pe listele mari
Alți algoritmi de sortare, cum ar fi sortarea rapidă, au performanțe mai bune în comparație cu sortarea prin selecție.