Mis on mullide sortimine?
Mullisorteerimine on sortimisalgoritm, mida kasutatakse loendiüksuste järjestamiseks kasvavas järjestuses, kõrvutades kahte kõrvuti asetsevat väärtust. Kui esimene väärtus on suurem kui teine, võtab esimene väärtus teise, teine väärtus aga esimese. Kui esimene väärtus on väiksem kui teine väärtus, siis vahetamist ei tehta.
Seda protsessi korratakse seni, kuni kõiki loendis olevaid väärtusi on võrreldud ja vajadusel vahetatud. Iga iteratsiooni nimetatakse tavaliselt läbimiseks. Mullisorteerimise läbimiste arv on võrdne loendis olevate elementide arvuga miinus üks.
Selles Pythoni mullide sorteerimise õpetuses saate teada:
- Mis on mullide sortimine?
- Mullide sorteerimise algoritmi rakendamine
- Optimeeritud mullide sorteerimise algoritm
- Visuaalne esitus
- Pythoni näited
- Koodi selgitus
- Mullide sortimise eelised
- Mullisort Puudused
- Mullisorteerimise keerukuse analüüs
Mullide sorteerimise algoritmi rakendamine
Jaotame rakenduse kolmeks (3) etapiks, nimelt probleemiks, lahenduseks ja algoritmiks, mida saame kasutada mis tahes keele koodi kirjutamiseks.
Probleem
Esemete loetelu on esitatud juhuslikus järjekorras ja me sooviksime need üksused korrastada
Mõelge järgmisele loendile:
[21,6,9,33,3]
Lahendus
Pöörake läbi loendi, kõrvutades kahte kõrvuti asetsevat elementi ja vahetades neid, kui esimene väärtus on suurem kui teine väärtus.
Tulemus peaks olema järgmine:
[3,6,9,21,33]
Algoritm
Mullide sorteerimise algoritm töötab järgmiselt
1. samm. Hankige elementide koguarv. Hankige antud loendis üksuste koguarv
2. samm. Määrake tehtavate välimiste läbipääsude arv (n - 1). Selle pikkus on loetelu miinus üks
Samm 3) Sisemise läbimise (n - 1) kordamine välise läbipääsu korral 1. Hankige esimese elemendi väärtus ja võrrelge seda teise väärtusega. Kui teine väärtus on väiksem kui esimene väärtus, vahetage positsioonid
Samm 4) Korrake 3. sammu, kuni jõuate välimise läbipääsuni (n - 1). Hankige loendi järgmine element ja korrake 3. etapis tehtud toimingut, kuni kõik väärtused on paigutatud õiges kasvavas järjekorras.
5. samm. Tagastage tulemus, kui kõik söödud on tehtud. Tagastab sorditud loendi tulemused
Samm 6) Algoritmi optimeerimine
Vältige tarbetuid sisepääse, kui loend või külgnevad väärtused on juba sorteeritud. Näiteks kui pakutav loend sisaldab juba elemente, mis on järjestatud kasvavas järjekorras, siis võime silmus varakult katkestada.
Optimeeritud mullide sorteerimise algoritm
Vaikimisi võrreldakse Pythoni mullide sortimise algoritmis kõiki loendis olevaid üksusi, hoolimata sellest, kas loend on juba sorteeritud või mitte. Kui antud loend on juba sorteeritud, on kõigi väärtuste võrdlemine aja ja ressursside raiskamine.
Mullisordi optimeerimine aitab meil vältida tarbetuid kordusi ning säästa aega ja ressursse.
Näiteks kui esimene ja teine üksus on juba sorditud, siis pole vaja ülejäänud väärtusi itereerida. Iteratsioon lõpetatakse ja järgmine käivitatakse, kuni protsess on lõpule viidud, nagu on näidatud allpool olevas mullide sorteerimise näites.
Optimeerimine toimub järgmiste sammude abil
Samm 1) Looge lipumuutuja, mis jälgib, kas siseringis on toimunud vahetusi
2. samm. Kui väärtused on positsioone vahetanud, jätkake järgmise iteratsiooniga
3. samm. Kui eelised pole positsioone vahetanud, lõpetage sisemine silmus ja jätkake välimise silmusega.
Optimeeritud mullide sortimine on tõhusam, kuna see täidab ainult vajalikke toiminguid ja jätab vahele need, mida pole vaja.
Visuaalne esitus
Viie elemendi loendi põhjal illustreerivad järgmised pildid, kuidas mull nende sortimisel väärtuste kaudu kordub
Järgmine pilt näitab sortimata loendit
Esimene kordus
Samm 1)
Väärtusi 21 ja 6 võrreldakse, et kontrollida, kumb on suurem kui teine.
21 on suurem kui 6, seega võtab 21 positsiooni, mille hõivab 6, samas kui 6 võtab positsiooni, mille hõivas 21
Meie muudetud loend näeb nüüd välja nagu ülaltoodud.
2. samm)
Võrreldakse väärtusi 21 ja 9.
21 on suurem kui 9, seega vahetame positsioonid 21 ja 9
Uus loend on nüüd nagu eespool
3. samm)
Suurema leidmiseks võrreldakse väärtusi 21 ja 33.
Väärtus 33 on suurem kui 21, seega vahetamist ei toimu.
4. samm)
Väärtusi 33 ja 3 võrreldakse suurema leidmiseks.
Väärtus 33 on suurem kui 3, seega vahetame nende positsioone.
Sorteeritud loend esimese iteratsiooni lõpus on nagu ülaltoodud
Teine kordus
Uus loend pärast teist kordust on järgmine
Kolmas kordus
Uus loetelu pärast kolmandat kordust on järgmine
Neljas kordus
Uus loetelu pärast neljandat kordust on järgmine
Pythoni näited
Järgmine kood näitab, kuidas rakendada mullisorteerimise algoritmi Pythonis.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Ülaltoodud mullide sorteerimisprogrammi käivitamine Pythonis annab järgmised tulemused
[6, 9, 21, 3, 33]
Koodi selgitus
Python Bubble Sort programmi koodi selgitus on järgmine
SIIN,
- Määrab funktsiooni bubbleSort, mis aktsepteerib parameetrit theSeq. Kood ei väljasta midagi.
- Saab massiivi pikkuse ja määrab väärtuse muutujale n. Kood ei väljasta midagi
- Käivitab for for loopi, mis käitab mullide sorteerimise algoritmi (n - 1) korda. See on välimine silmus. Kood ei väljasta midagi
- Määrab lipumuutuja, mida kasutatakse vahetuse toimumise tuvastamiseks. See on optimeerimise eesmärgil. Kood ei väljasta midagi
- Alustab sisemist silmust, mis võrdleb kõiki loendis olevaid väärtusi esimesest viimaseni. Kood ei väljasta midagi.
- Kasutab lauset if kontrollimaks, kas vasakpoolne väärtus on paremal paremal. Kood ei väljasta midagi.
- Määrab väärtuse Seq [j] ajalisele muutujale tmp, kui tingimus on tõene. Kood ei väljasta midagi
- Seq [j + 1] väärtus määratakse seq [j] positsioonile. Kood ei väljasta midagi
- Muutuja tmp väärtus määratakse positsioonile theSeq [j + 1]. Kood ei väljasta midagi
- Lipumuutujale määratakse väärtus 1, mis näitab vahetamise toimumist. Kood ei väljasta midagi
- Kasutab lauset if, et kontrollida, kas muutuja lipu väärtus on 0. Kood ei väljasta midagi
- Kui väärtus on 0, siis nimetame siseaasast välja astuvat katkestuslauset.
- Tagastab seqi väärtuse pärast selle sortimist. Kood väljastab sorditud loendi.
- Määrab muutuja el, mis sisaldab juhuslike arvude loendit. Kood ei väljasta midagi.
- Määrab funktsiooni bubbleSort väärtuse muutuvale tulemusele.
- Prindib muutuja tulemuse väärtuse.
Mullide sortimise eelised
Allpool on mõned mullide sortimise algoritmi eelised
- Sellest on lihtne aru saada
- See toimib väga hästi, kui loend on juba valmis või peaaegu sorditud
- See ei nõua ulatuslikku mälu.
- Algoritmi koodi on lihtne kirjutada
- Ruumivajadus on teiste sortimisalgoritmidega võrreldes minimaalne.
Mullisort Puudused
Allpool on mõned mullide sortimise algoritmi puudused
- Suurte loendite sortimisel ei toimi see hästi. See võtab liiga palju aega ja ressursse.
- Seda kasutatakse enamasti akadeemilistel eesmärkidel ja mitte reaalses maailmas.
- Loendi sortimiseks vajalike toimingute arv on suurusjärgus n 2
Mullisorteerimise keerukuse analüüs
Keerukust on kolme tüüpi:
1) Sorteeri keerukus
Sorteerimise keerukust kasutatakse täitmisaegade ja ruumi hulga väljendamiseks, mis kulub loendi sortimiseks. Mullide sortimine teeb (n - 1) kordusi loendi sortimiseks, kus n on loendi elementide koguarv.
2) Aja keerukus
Mullisordi ajaline keerukus on O (n 2 )
Aja keerukust saab liigitada järgmiselt:
- Halvimal juhul - siin on esitatud loetelu kahanevas järjekorras. Algoritm teostab maksimaalse hukkamiste arvu, mis on väljendatud kui [Big-O] O (n 2 )
- Parimal juhul - see juhtub siis, kui esitatud loend on juba sorteeritud. Algoritm teostab minimaalse hukkamiste arvu, mis on väljendatud [Big-Omega] Ω (n)
- Keskmine juhtum - see juhtub siis, kui loend on juhuslikus järjekorras. Keskmine keerukus on esitatud [suurteeta] ⊝ (n 2 )
3) Ruumi keerukus
Ruumi keerukus mõõdab loendi sortimiseks vajaliku lisaruumi hulka. Mullide sortimine nõuab väärtuste vahetamiseks kasutatava ajamuutuja jaoks ainult ühte (1) lisaruumi. Seetõttu on selle ruumiline keerukus O (1).
Kokkuvõte
- Mullide sorteerimise algoritm töötab, kui võrrelda kahte kõrvuti asetsevat väärtust ja vahetada neid, kui vasakpoolne väärtus on väiksem kui paremal olev väärtus.
- Mullide sorteerimise algoritmi rakendamine on Pythoni puhul suhteliselt lihtne. Kõik, mida peate kasutama, on tsüklite ja if-lausete jaoks.
- Probleem, mille mullide sorteerimise algoritm lahendab, on juhuslike üksuste loendi võtmine ja selle muutmine järjestatud loendiks.
- Mullide sortimise algoritm andmestruktuuris toimib kõige paremini siis, kui loend on juba sorteeritud, kuna see täidab minimaalset arvu kordusi.
- Mullide sorteerimise algoritm ei toimi hästi, kui loend on vastupidises järjekorras.
- Mullija sordil on O (n 2 ) ajaline keerukus ja O ( 1 ) ruumi keerukus
- Mullitavate sortide algoritm sobib kõige paremini akadeemilistel eesmärkidel ja mitte reaalsetes rakendustes.
- Optimeeritud mullide sortimine muudab algoritmi efektiivsemaks, jättes tarbetud iteratsioonid vahele juba sorteeritud väärtuste kontrollimisel.