Bubble Sorteerimisalgoritm koos Python kasutades loendi näidet

Mis on a Bubble Sorteerida?

Bubble Sorteeri on sortimisalgoritm, mida kasutatakse loendiüksuste sortimiseks kasvavas järjekorras kahe külgneva väärtuse võrdlemise teel. Kui esimene väärtus on teisest väärtusest suurem, võtab esimene väärtus teise väärtuse positsiooni, teine ​​väärtus aga esimese väärtuse positsiooni. Kui esimene väärtus on teisest väärtusest väiksem, siis vahetust ei toimu.ping tehakse.

Seda protsessi korratakse seni, kuni loendi kõiki väärtusi on võrreldud ja vajadusel vahetatud. Iga iteratsiooni nimetatakse tavaliselt läbimiseks. Läbimiste arv mulli sortimisel võrdub loendi elementide arvuga, millest on lahutatud üks.

Selle Bubble Sorteerimine Python juhendaja saate teada, millist probleemi see lahendab, selle optimeeritud vormi, samm-sammult visuaalse läbimängu, töötava Python programm ja selle jõudlusomadused.

Rakendades Bubble Sorteerimisalgoritm

Jagame implementatsiooni kolmeks (3) etapiks: probleem, lahendus ja algoritm, mida saame kasutada mis tahes keele koodi kirjutamiseks.

Probleem

Esemete loend on antud juhuslikus järjekorras ja me soovime need korrapäraselt paigutada.

Kaaluge järgmist loendit:

[21, 6, 9, 33, 3]

lahendus

Käi loendis kaks külgnevat elementi iteratiivselt läbi ja võrdle need omavahel.ping neid, kui esimene väärtus on teisest väärtusest suurem.

Tulemus peaks olema järgmine:

[3, 6, 9, 21, 33]

Algoritm

Mullide sortimise algoritm töötab järgmiselt:

Step 1) Leia elementide koguarv. Leia antud loendi üksuste koguarv.

Step 2) Määrake tehtavate välimiste läbimiste arv (n – 1). Selle pikkus on loend miinus üks.

Step 3) Soorita välimise 1. käiguga sisemisi läbimisi (n – 1) korda. Leia esimese elemendi väärtus ja võrdle seda teise väärtusega. Kui teine ​​väärtus on esimesest väiksem, siis vaheta kohad.

Step 4) Korda 3. sammu käike kuni välimise käiguni (n – 1). Leia loendist järgmine element ja korda 3. sammus sooritatud toimingut, kuni kõik väärtused on paigutatud õigesse kasvavasse järjekorda.

Step 5) Tagasta tulemus, kui kõik läbimised on tehtud. Tagasta sorteeritud loendi tulemused.

Step 6) Optimeerimisalgoritm.

Vältige tarbetuid sisemisi läbimisi, kui loend või külgnevad väärtused on juba sorteeritud. Näiteks kui esitatud loend sisaldab juba kasvavas järjekorras järjestatud elemente, saame tsükli varakult katkestada.

Optimaalne Bubble Sorteerimisalgoritm

Vaikimisi sorteeritakse mullide algoritm sisse Python võrdleb kõiki loendis olevaid üksusi olenemata sellest, kas loend on juba sorteeritud või mitte. Kui antud loend on juba sorteeritud, on kõigi väärtuste võrdlemine aja ja ressursi raiskamine.

Mullide sortimise optimeerimine aitab meil vältida tarbetuid iteratsioone ning säästa aega ja ressursse.

Näiteks kui esimene ja teine ​​üksus on juba sorteeritud, ei ole vaja ülejäänud väärtusi itereerida. Iteratsioon lõpetatakse ja järgmine käivitatakse, kuni protsess on lõpule viidud, nagu allpool näidatud Bubble Sordi näide.

Optimeerimine toimub järgmiste sammude abil:

Step 1) Loo lipumuutuja, mis jälgib vahetuste toimumistping on toimunud sisemises tsüklis.

Step 2) Kui väärtused on positsioone vahetanud, jätkake järgmise iteratsiooniga.

Step 3) Kui väärtused pole positsioone vahetanud, lõpetage sisemine tsükkel ja jätkake välimise tsükliga.

Optimeeritud mullide sortimine on tõhusam, kuna see täidab ainult vajalikud toimingud ja jätab vahele need, mida pole vaja.

Visuaalne esitus

Järgnevad pildid illustreerivad, kuidas mullsortimine väärtusi sortimisel läbi käib, kui on antud viiest elemendist koosnev loend.

Järgmisel pildil on näha sortimata nimekiri:

Esimene iteratsioon

Step 1)

Väärtusi 21 ja 6 võrreldakse, et kontrollida, milline neist on teisest suurem.

21 on suurem kui 6, seega võtab 21 endale koha, mille hõivas 6, samas kui 6 võtab endale koha, mille hõivas 21.

Meie muudetud loend näeb nüüd välja nagu ülaltoodud.

Step 2)

Väärtusi 21 ja 9 võrreldakse.

21 on suurem kui 9, seega vahetame arvude 21 ja 9 kohad.

Uus nimekiri on nüüd selline, nagu ülalpool.

Step 3)

Suurema leidmiseks võrreldakse väärtusi 21 ja 33.

Väärtus 33 on suurem kui 21, seega vahetust ei toimu.ping leiab aset.

Step 4)

Suurema leidmiseks võrreldakse väärtusi 33 ja 3.

Väärtus 33 on suurem kui 3, seega vahetame nende positsioonid.

Esimese iteratsiooni lõpus olev sorteeritud loend on nagu ülaltoodud.

Teine iteratsioon

Pärast teist iteratsiooni on uus nimekiri järgmine:

Kolmas iteratsioon

Pärast kolmandat iteratsiooni on uus nimekiri järgmine:

Neljas iteratsioon

Pärast neljandat iteratsiooni on uus nimekiri järgmine:

Python Näited

Järgmine kood näitab, kuidas rakendada Bubble Sordi algoritm sisse Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

Ülaltoodud mulli sortimise programmi käivitamine Python annab järgmised tulemused:

[3, 6, 9, 21, 33]

Code Selgitus

Selgitus selle kohta Python BubblProgrammi sortimiskood on järgmine:

SIIN,

1. Määratleb funktsiooni bubbleSort, mis aktsepteerib parameetri theSeq. Kood ei väljasta midagi.
2. Hangib massiivi pikkuse ja määrab selle väärtuse muutujale n. Kood ei väljasta midagi.
3. Käivitab for-tsükli, mis käivitab mullsortimise algoritmi (n – 1) korda. See on välimine tsükkel. Kood ei anna väljundit.
4. Määratleb lipumuutuja, mida kasutatakse vahetuse toimumise või mitte toimumise tuvastamiseks. See on optimeerimise eesmärgil. Kood ei anna väljundit.
5. Käivitab sisemise tsükli, mis võrdleb kõiki loendi väärtusi esimesest viimaseni. Kood ei väljasta midagi.
6. Kasutab if-lauset, et kontrollida, kas vasakul olev väärtus on suurem kui vahetult paremal. Kood ei väljasta midagi.
7. Kui tingimus annab tulemuseks tõese (true), määrab ajalisele muutujale tmp theSeq[j] väärtuse. Kood ei väljasta midagi.
8. Seq[j + 1] väärtus määratakse Seq[j] positsioonile. Kood ei väljasta midagi.
9. Muutuja tmp väärtus määratakse positsioonile theSeq[j + 1]. Kood ei väljasta midagi.
10. Muutujale lipp omistatakse väärtus 1, et näidata vahetuse toimumist. Kood ei väljasta midagi.
11. Kasutab if-lauset, et kontrollida, kas muutuja flag väärtus on 0. Kood ei väljasta midagi.
12. Kui väärtus on 0, siis kutsume sisemisest tsüklist välja astuvat katkestuslauset.
13. Tagastab theSeq väärtuse pärast selle sortimist. Kood väljastab sorteeritud loendi.
14. Määratleb muutuja el, mis sisaldab juhuslike arvude loendit. Kood ei väljasta midagi.
15. Määrab muutuja tulemusele funktsiooni bubbleSort väärtuse.
16. Prindib muutuja tulemuse väärtuse.

Bubble sorti eeliseid

Mullide sortimise algoritmi eelised on järgmised:

• Seda on lihtne mõista.
• See toimib väga hästi, kui nimekiri on juba või peaaegu sorteeritud.
• See ei nõua suurt mälu.
• Algoritmi koodi on lihtne kirjutada.
• Ruumivajadus on teiste sorteerimisalgoritmidega võrreldes minimaalne.

Bubble sorteerida Puudused

Järgnevalt on toodud mõned mullide sortimise algoritmi puudused:

• See ei toimi suurte loendite sortimisel hästi. See võtab liiga palju aega ja ressursse.
• Seda kasutatakse enamasti akadeemilistel eesmärkidel, mitte reaalses elus.
• Loendi sortimiseks vajalik sammude arv on suurusjärgus n².

Keerukuse analüüs Bubble Sorteeri

On kolme tüüpi keerukust:

1) Sortimise keerukus

Sorteerimise keerukust kasutatakse loendi sortimiseks kuluva aja ja ruumi väljendamiseks. Mullsortimine teeb loendi sortimiseks (n – 1) iteratsiooni, kus n on loendi elementide koguarv.

2) Ajaline keerukus

Mullide sorteerimise ajaline keerukus on O(n²).

Ajalisi keerukusi võib liigitada järgmiselt:

• 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 antud loend on juba sorteeritud. Algoritm sooritab minimaalse arvu täitmisi, mida väljendatakse kui [Big-Omega] Ω(n).
• Keskmine juhtum – see juhtub siis, kui loend on juhuslikus järjekorras. Keskmine keerukus on esitatud kui [Big-teeta] ⊝(n²).

3) Ruumi keerukus

Ruumi keerukus mõõdab loendi sortimiseks vajaliku lisaruumi hulka. Mullsortimine nõuab swapi jaoks kasutatava ajalise muutuja jaoks ainult ühte (1) lisaruumi.ping väärtused. Seega on selle ruumi keerukus O(1).

KKK