Valiku sortimine: Algoritmi selgitamine Python Koodinäide

Mis on valiku sortimine?

VALIK SORTI on võrdlussorteerimisalgoritm, mida kasutatakse juhusliku üksuste loendi sortimiseks kasvavas järjekorras. Võrdlus ei nõua palju lisaruumi. See nõuab ajalise muutuja jaoks ainult ühte lisamälu.

Seda tuntakse kui kohas sorteerimine. Valiku sortimise ajaline keerukus on O(n²) kus n on loendis olevate üksuste koguarv. Ajaline keerukus mõõdab loendi sortimiseks vajalike iteratsioonide arvu. Loend on jagatud kaheks osaks: esimene loend sisaldab sorteeritud üksusi, teine loend aga sortimata üksusi.

Vaikimisi on sorteeritud loend tühi ja sortimata loend sisaldab kõiki elemente. Seejärel otsitakse sortimata loendist minimaalset väärtust, mis seejärel paigutatakse sorteeritud loendisse. Seda protsessi korratakse, kuni kõik väärtused on võrreldud ja sorteeritud.

Kuidas valiku sortimine töötab?

Sorteerimata partitsiooni esimest üksust võrreldakse kõigi parempoolsete väärtustega, et kontrollida, kas see on minimaalne väärtus. Kui see ei ole miinimumväärtus, vahetatakse selle asukoht minimaalse väärtusega.

Näide

Näiteks kui miinimumväärtuse indeks on 3, asetatakse indeksiga 3 elemendi väärtus indeksisse 0, samas kui indeksis 0 olnud väärtus paigutatakse indeksisse 3. Kui sortimata partitsiooni esimene element on minimaalne väärtus, siis tagastab see oma positsioonid.
Minimaalseks väärtuseks määratud element teisaldatakse seejärel vasakpoolsesse partitsiooni, mis on sorteeritud loend.
Jaotatud poolel on nüüd üks element, samas kui jaotamata poolel on (n – 1) elementi, kus n on loendis olevate elementide koguarv. Seda protsessi korratakse ikka ja jälle, kuni kõiki üksusi on võrreldud ja nende väärtuste alusel sorteeritud.

Probleemi määratlus

Juhuslikus järjekorras olevate elementide loend tuleb sortida kasvavas järjekorras. Võtke näiteks järgmine loend.

[21,6,9,33,3]

Ülaltoodud loend tuleks järgmiste tulemuste saamiseks sorteerida

[3,6,9,21,33]

Lahendus (algoritm)

Step 1) Hankige n väärtus, mis on massiivi kogusuurus

Step 2) Jagage loend sorteeritud ja sortimata osadeks. Sorditud jaotis on algselt tühi, sortimata jaotis sisaldab aga kogu loendit

Step 3) Valige jaotamata jaotisest minimaalne väärtus ja asetage see sorteeritud jaotisesse.

Step 4) Korrake protsessi (n–1) korda, kuni kõik loendi elemendid on sorteeritud.

Visuaalne esitus

Viie elemendi loendis illustreerivad järgmised pildid, kuidas valiku sortimise algoritm väärtuste sortimisel kordab.

Järgmine pilt näitab sortimata loendit

Step 1)

Esimest väärtust 21 võrreldakse ülejäänud väärtustega, et kontrollida, kas see on minimaalne väärtus.

3 on minimaalne väärtus, seega positsioonid 21 ja 3 vahetatakse. Rohelise taustaga väärtused tähistavad loendi sorteeritud sektsiooni.

Step 2)

Väärtust 6, mis on sortimata partitsiooni esimene element, võrreldakse ülejäänud väärtustega, et teha kindlaks, kas on olemas väiksem väärtus

Väärtus 6 on minimaalne väärtus, seega säilitab see oma positsiooni.

Step 3)

Sortimata loendi esimest elementi väärtusega 9 võrreldakse ülejäänud väärtustega, et kontrollida, kas see on minimaalne väärtus.

Väärtus 9 on minimaalne väärtus, seega säilitab see oma positsiooni sorteeritud partitsioonis.

Step 4)

Väärtust 33 võrreldakse ülejäänud väärtustega.

Väärtus 21 on väiksem kui 33, seega vahetatakse positsioone ülaltoodud uue loendi koostamiseks.

Step 5)

Meil on jaotamata loendis ainult üks väärtus. Seetõttu on see juba sorteeritud.

Lõplik nimekiri sarnaneb ülaloleval pildil kujutatuga.

Valik Sorteeri programm kasutades Python 3

Järgmine kood näitab valiku sortimise rakendamist kasutades 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))

Ülaltoodud koodi käivitamine annab järgmised tulemused

[3, 6, 9, 21, 33]

Koodi selgitus

Koodi selgitus on järgmine

Siin on koodi selgitus:

Määrab funktsiooni nimega selectionSort
Hangib loendis olevate elementide koguarvu. Vajame seda väärtuste võrdlemisel tehtavate läbimiste arvu määramiseks.
Väline silmus. Kasutab tsüklit loendi väärtuste läbimiseks. Iteratsioonide arv on (n – 1). N väärtus on 5, seega (5 – 1) annab meile 4. See tähendab, et välimised iteratsioonid sooritatakse 4 korda. Igas iteratsioonis määratakse muutuja i väärtus muutujale minValueIndex
Sisemine silmus. Kasutab tsüklit vasakpoolseima väärtuse võrdlemiseks teiste parempoolsete väärtustega. Kuid j väärtus ei alga indeksist 0. See algab (i + 1). See välistab väärtused, mis on juba sorteeritud, nii et keskendume üksustele, mida pole veel sorteeritud.
Otsib sortimata loendist minimaalse väärtuse ja asetab selle õigesse kohta
Värskendab minValueIndexi väärtust, kui vahetustingimus on tõene
Võrdleb indeksinumbrite minValueIndex ja i väärtusi, et näha, kas need pole võrdsed
Vasakpoolseim väärtus salvestatakse ajalisse muutujasse
Parempoolne madalam väärtus võtab esimese positsiooni
Ajalises väärtuses salvestatud väärtus salvestatakse positsioonile, mida varem hoidis miinimumväärtus
Tagastab sorditud loendi funktsiooni tulemusena
Loob loendi el, mis sisaldab juhuslikke numbreid
Printige sorteeritud loend pärast parameetrina el oleva valiku Sort funktsiooni kutsumist.

Valiku sortimise ajaline keerukus

Sortimise keerukust kasutatakse loendi sortimiseks kuluvate täitmiskordade arvu väljendamiseks. Rakendusel on kaks silmust.

Välistsükkel, mis valib loendist väärtused ükshaaval, käivitatakse n korda, kus n on loendis olevate väärtuste koguarv.

Sisemine tsükkel, mis võrdleb välise tsükli väärtust ülejäänud väärtustega, käivitatakse samuti n korda, kus n on loendi elementide koguarv.

Seetõttu on täitmiste arv (n * n), mida saab väljendada ka O(n²).

Valiku sorteerimisel on kolm keerukuse kategooriat, nimelt;

Halvimal juhul – siin on esitatud loend kahanevas järjekorras. Algoritm teostab maksimaalse arvu täitmisi, mis on väljendatud kui [Big-O] O(n²)
Parim juhtum – see juhtub siis, kui esitatud loend on juba sorteeritud. Algoritm teostab minimaalse arvu täitmisi, mis on väljendatud kui [Big-Omega] ?(n²)
Keskmine juhtum – see juhtub siis, kui loend on juhuslikus järjekorras. Keskmist keerukust väljendatakse [Big-teeta] ?(n²)

Valiku sortimisel on ruumi keerukus O(1), kuna see nõuab väärtuste vahetamiseks üht ajalist muutujat.

Millal valikusortimist kasutada?

Valiku sortimist on kõige parem kasutada, kui soovite:

Peate sorteerima väikese loendi üksustest kasvavas järjekorras
Kui väärtuste vahetamise kulud on ebaolulised
Seda kasutatakse ka siis, kui peate veenduma, et kõik loendis olevad väärtused on kontrollitud.

Valikusortimise eelised

Valiku sortimise eelised on järgmised

See toimib väikestes loendites väga hästi
See on kohapealne algoritm. See ei nõua sorteerimiseks palju ruumi. Ajutise muutuja hoidmiseks on vaja ainult ühte lisaruumi.
See toimib hästi juba sorteeritud üksuste puhul.

Valikusortimise puudused

Valiku sortimise puudused on järgmised.

Suurte loenditega töötades töötab see halvasti.
Sorteerimisel tehtud iteratsioonide arv on n-ruudus, kus n on loendi elementide koguarv.
Muudel algoritmidel, näiteks kiirsortimisel, on parem jõudlus võrreldes valiku sorteerimisega.

kokkuvõte

Valiku sortimine on kohapealne võrdlusalgoritm, mida kasutatakse juhusliku loendi sortimiseks järjestatud loendisse. Selle ajaline keerukus on O(n²)
Loend on jagatud kaheks osaks, sorteeritud ja sortimata. Minimaalne väärtus valitakse sortimata sektsioonist ja asetatakse sorteeritud sektsiooni.
Seda korratakse seni, kuni kõik üksused on sorteeritud.
Pseudokoodi juurutamine sisse Python 3 hõlmab kahe tsükli ja if-lausete kasutamist, et kontrollida, kas vahetamine on vajalik
Ajaline keerukus mõõdab loendi sortimiseks vajalike sammude arvu.
Halvimal juhul ilmneb ajaline keerukus, kui loend on kahanevas järjekorras. Selle ajaline keerukus on [Big-O] O(n²)
Parimal juhul ajaline keerukus ilmneb siis, kui loend on juba kasvavas järjekorras. Selle ajaline keerukus on [Big-Omega] ?(n²)
Juhtumi keskmine keerukus ilmneb siis, kui loend on juhuslikus järjekorras. Selle ajaline keerukus on [Big-teeta] ?(n²)
Valiku sortimist on kõige parem kasutada siis, kui sortitavate üksuste loend on väike, väärtuste vahetamise maksumus ei oma tähtsust ja kõigi väärtuste kontrollimine on kohustuslik.
Valiku sortimine ei toimi suurtes loendites hästi
Muudel sortimisalgoritmidel, näiteks kiirsortimisel, on parem jõudlus võrreldes valiku sortimisega.