Algoritm de sortare prin selecție cu Python Code Exemplu

⚡ Rezumat inteligent

Sortarea prin selecție este un algoritm de comparație in-place care sortează o listă aleatorie în ordine crescătoare prin selectarea repetată a celei mai mici valori nesortate și mutarea acesteia în secțiunea sortată. Această resursă explică... Python exemplu și complexitatea sa temporală.

🎯 Ideea de bază: Sortarea prin selecție găsește în mod repetat valoarea minimă din secțiunea nesortată și o mută în secțiunea sortată.
🧠 Pe loc: Sortează folosind o singură variabilă temporară suplimentară, rezultând o complexitate spațială de O(1).
⏱️ Complexitatea timpului: Se execută în timp O(n²) în cele mai rele cazuri, cele mai bune și cele medii, datorită buclelor imbricate.
🐍 Python Exemplu: O funcție scurtă cu două bucle schimbă minimul în locul său până când lista este sortată.
🇧🇷 Cea mai bună utilizare: Se potrivește listelor mici unde costul de schimb este scăzut și fiecare valoare trebuie verificată.

Citește mai mult

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]

Code Explicație

Explicația pentru cod este următoarea

Aici este Code explicaţie:

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 când se efectuează swap-ulping condiția 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 – aceasta se întâmplă atunci când lista furnizată este deja sortată. Algoritmul efectuează 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 prin selecție are o complexitate spațială de O(1), deoarece necesită o variabilă temporală utilizată pentru swap.ping valori.

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 schimbuluiping valorile sunt nesemnificative
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.

Întrebări frecvente

Sortarea prin selecție nu este stabilă în forma sa de bază, deoareceping Elementele distale pot schimba ordinea relativă a cheilor egale. O variantă de listă înlănțuită sau o deplasare atentă o poate face stabilă, dar versiunea standard a matricei este instabilă.

Sortarea prin selecție scanează partea nesortată pentru a găsi minimul și o schimbă la locul ei, efectuând câteva schimbări. Sortarea prin inserție preia fiecare element și deplasează elementele sortate mai mari spre dreapta pentru a-l insera. Sortarea prin inserție este de obicei mai rapidă pentru datele aproape sortate.

Sortarea prin selecție efectuează cel mult n-1 permutare pentru o listă de n elemente, câte una per trecere. Acest număr redus de permutare o face utilă atunci când scrierea în memorie este costisitoare, chiar dacă tot efectuează O(n²) comparații.

Tutorii cu inteligență artificială pot tracSortarea pas cu pas a selecției, animarea fiecărei schimbări și chestionarea complexității timpului. Acest feedback interactiv îi ajută pe începători să înțeleagă cum este selectat și mutat minimul în timpul fiecărei treceri.

Da. Asistenții de codare bazați pe inteligență artificială pot genera sortare prin selecție în multe limbi, pot explica fiecare linie și pot sugera algoritmi mai eficienți, cum ar fi quicksort, atunci când datele de intrare cresc. Testați întotdeauna codul generat înainte de a-l utiliza.