Algoritmus bublinového triedenia s Pythonom pomocou príkladu zoznamu

Obsah:

Anonim

Čo je to triedenie bublín?

Bubble Sort je triediaci algoritmus, ktorý sa používa na triedenie položiek zoznamu vzostupne podľa porovnania dvoch susedných hodnôt. Ak je prvá hodnota vyššia ako druhá hodnota, prvá hodnota zaberá pozíciu druhej hodnoty, zatiaľ čo druhá hodnota zaberá pozíciu prvej hodnoty. Ak je prvá hodnota nižšia ako druhá hodnota, potom sa zámena nerobí.

Tento proces sa opakuje, kým sa neporovnajú všetky hodnoty v zozname a v prípade potreby sa nevymenia. Každá iterácia sa zvyčajne nazýva priechod. Počet prechodov v triedení podľa bublín sa rovná počtu prvkov v zozname mínus jeden.

V tomto tutoriáli Bubble Sorting in Python sa dozviete:

  • Čo je to triedenie bublín?
  • Implementácia algoritmu triedenia bublín
  • Optimalizovaný algoritmus triedenia bublín
  • Vizuálne znázornenie
  • Príklady Pythonu
  • Vysvetlenie kódu
  • Výhody triedenia bubliniek
  • Nevýhody bublinového triedenia
  • Analýza zložitosti triedenia bublín

Implementácia algoritmu triedenia bublín

Implementáciu rozdelíme do troch (3) krokov, a to problém, riešenie a algoritmus, ktorý môžeme použiť na napísanie kódu pre akýkoľvek jazyk.

Problém

Zoznam položiek je uvedený v náhodnom poradí a my by sme chceli tieto položky usporiadať usporiadane

Zvážte nasledujúci zoznam:

[21,6,9,33,3]

Riešenie

Iteráciou prechádzajte zoznamom, ktorý porovnáva dva susedné prvky a vymieňa ich, ak je prvá hodnota vyššia ako druhá hodnota.

Výsledok by mal byť nasledovný:

[3,6,9,21,33]

Algoritmus

Algoritmus triedenia bublín funguje nasledovne

Krok 1) Získajte celkový počet prvkov. Získajte celkový počet položiek v danom zozname

Krok 2) Určte počet vonkajších priechodov (n - 1), ktoré sa majú vykonať. Jeho dĺžka je zoznam mínus jedna

Krok 3) Vykonajte vnútorné priechody (n - 1) krát pre vonkajší priechod 1. Získajte hodnotu prvého prvku a porovnajte ju s druhou hodnotou. Ak je druhá hodnota menšia ako prvá hodnota, potom polohy vymeňte

Krok 4) Opakujte kroky 3, až kým nedosiahnete vonkajší priechod (n - 1). Získajte nasledujúci prvok v zozname a potom opakujte postup, ktorý bol vykonaný v kroku 3, kým všetky hodnoty nebudú umiestnené v správnom vzostupnom poradí.

Krok 5) Po dokončení všetkých pokusov vráťte výsledok. Vráti výsledky zoradeného zoznamu

Krok 6) Optimalizujte algoritmus

Ak sú zoznam alebo susedné hodnoty už zoradené, vyhnite sa zbytočným vnútorným prechodom. Napríklad, ak poskytnutý zoznam už obsahuje prvky, ktoré boli zoradené vzostupne, môžeme slučku prerušiť skôr.

Optimalizovaný algoritmus triedenia bublín

Algoritmus pre triedenie bublín v Pythone štandardne porovnáva všetky položky v zozname bez ohľadu na to, či je zoznam už zoradený alebo nie. Ak je daný zoznam už zoradený, porovnanie všetkých hodnôt je stratou času a zdrojov.

Optimalizácia triedenia bublín nám pomáha vyhnúť sa zbytočným iteráciám a ušetriť čas a zdroje.

Napríklad, ak sú prvá a druhá položka už zoradené, nie je potrebné opakovať zvyšné hodnoty. Iterácia je ukončená a ďalšia je iniciovaná, kým sa proces nedokončí, ako je to znázornené v príklade Bubble Sort.

Optimalizácia sa vykonáva pomocou nasledujúcich krokov

Krok 1) Vytvorte premennú príznaku, ktorá sleduje, či vo vnútornej slučke došlo k prehodeniu

Krok 2) Ak hodnoty prehodili pozície, pokračujte na ďalšiu iteráciu

Krok 3) Ak dávky nevymenili pozíciu, ukončite vnútornú slučku a pokračujte vonkajšou slučkou.

Optimalizované triedenie bublín je efektívnejšie, pretože vykonáva iba potrebné kroky a preskočí tie, ktoré sa nevyžadujú.

Vizuálne znázornenie

Nasledujúce obrázky, ktoré obsahujú zoznam piatich prvkov, ilustrujú, ako triedenie bublín iteruje cez hodnoty pri ich triedení

Nasledujúci obrázok zobrazuje netriedený zoznam

Prvá iterácia

Krok 1)

Hodnoty 21 a 6 sa porovnajú s kontrolou, ktorá z nich je väčšia ako druhá.

21 je väčšie ako 6, takže 21 zaujme pozíciu obsadenú 6, zatiaľ čo 6 zaujme pozíciu, ktorú obsadilo 21

Náš upravený zoznam teraz vyzerá ako ten vyššie.

Krok 2)

Hodnoty 21 a 9 sa porovnávajú.

21 je väčšie ako 9, takže si zameníme polohy 21 a 9

Nový zoznam je teraz uvedený vyššie

Krok 3)

Hodnoty 21 a 33 sa porovnajú s cieľom nájsť väčšiu.

Hodnota 33 je väčšia ako 21, takže k zámene nedochádza.

Krok 4)

Hodnoty 33 a 3 sa porovnajú s cieľom nájsť väčšiu.

Hodnota 33 je väčšia ako 3, takže ich polohy zameníme.

Zoradený zoznam na konci prvej iterácie je podobný vyššie uvedenému

Druhá iterácia

Nový zoznam po druhej iterácii je nasledovný

Tretia iterácia

Nový zoznam po tretej iterácii je nasledovný

Štvrtá iterácia

Nový zoznam po štvrtej iterácii je nasledovný

Príklady Pythonu

Nasledujúci kód ukazuje, ako implementovať algoritmus Bubble Sort v Pythone.

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)

Vykonanie vyššie uvedeného programu triedenia bublín v Pythone vedie k nasledujúcim výsledkom

[6, 9, 21, 3, 33]

Vysvetlenie kódu

Vysvetlenie kódu programu Python Bubble Sort je nasledovné

TU,

  1. Definuje funkciu bubbleSort, ktorá akceptuje parameter theSeq. Z kódu nevychádza nič.
  2. Získa dĺžku poľa a priradí hodnotu premennej n. Z kódu nevychádza nič
  3. Spustí cyklus for, ktorý spustí algoritmus triedenia bublín (n - 1) krát. Toto je vonkajšia slučka. Z kódu nevychádza nič
  4. Definuje príznakovú premennú, ktorá sa použije na určenie, či došlo k zámene alebo nie. Je to z dôvodu optimalizácie. Z kódu nevychádza nič
  5. Spustí vnútornú slučku, ktorá porovnáva všetky hodnoty v zozname od prvej po poslednú. Z kódu nevychádza nič.
  6. Pomocou príkazu if skontroluje, či je hodnota na ľavej strane väčšia ako hodnota na pravej strane. Z kódu nevychádza nič.
  7. Priradí hodnotu seq [j] časovej premennej tmp, ak sa stav vyhodnotí ako pravdivý. Z kódu nevychádza nič
  8. Hodnota theSeq [j + 1] je priradená k polohe theSeq [j]. Z kódu nevychádza nič
  9. Hodnota premennej tmp je priradená pozícii theSeq [j + 1]. Z kódu nevychádza nič
  10. Príznakovej premennej je priradená hodnota 1, ktorá označuje, že došlo k zámene. Z kódu nevychádza nič
  11. Používa príkaz if na kontrolu, či je hodnota príznaku premennej 0. Kód nevydáva nič
  12. Ak je hodnota 0, potom zavoláme príkaz break, ktorý vykročí z vnútornej slučky.
  13. Vráti hodnotu parametra theSeq po jeho zoradení. Výstupom kódu je zoradený zoznam.
  14. Definuje premennú el, ktorá obsahuje zoznam náhodných čísel. Z kódu nevychádza nič.
  15. Priradí hodnotu funkcie bubbleSort premenlivému výsledku.
  16. Vytlačí hodnotu výsledku premennej.

Výhody triedenia bubliniek

Nasleduje niekoľko výhod algoritmu bublinového triedenia

  • Je ľahké to pochopiť
  • Podáva veľmi dobré výsledky, keď je zoznam už alebo takmer zoradený
  • Nevyžaduje rozsiahlu pamäť.
  • Je ľahké napísať kód pre algoritmus
  • Priestorové požiadavky sú v porovnaní s inými triediacimi algoritmami minimálne.

Nevýhody bublinového triedenia

Nasleduje niekoľko nevýhod algoritmu bublinového triedenia

  • Pri triedení veľkých zoznamov nefunguje dobre. Trvá to príliš veľa času a zdrojov.
  • Väčšinou sa používa na akademické účely, a nie na použitie v reálnom svete.
  • Počet krokov potrebných na zoradenie zoznamu je v poradí n 2

Analýza zložitosti triedenia bublín

Existujú tri typy zložitosti:

1) Zložitosť triedenia

Zložitosť zoradenia sa používa na vyjadrenie množstva časov vykonania a priestoru, ktorý je potrebný na zoradenie zoznamu. Triedenie bublín robí (n - 1) iterácií na triedenie zoznamu, kde n je celkový počet prvkov v zozname.

2) Časová zložitosť

Časová zložitosť druhu bubliny je O (n 2 )

Časovú zložitosť možno kategorizovať ako:

  • Najhorší prípad - tu je uvedený zoznam zostupne. Algoritmus vykonáva maximálny počet vykonaní, ktorý je vyjadrený ako [Big-O] O (n 2 )
  • Najlepší prípad - nastane, keď je poskytnutý zoznam už zoradený. Algoritmus vykonáva minimálny počet vykonaní, ktorý je vyjadrený ako [Big-Omega] Ω (n)
  • Priemerný prípad - k tomu dôjde, keď je zoznam v náhodnom poradí. Priemerná zložitosť je vyjadrená ako [Big-theta] ⊝ (n 2 )

3) Zložitosť priestoru

Komplexnosť priestoru meria veľkosť extra priestoru, ktorý je potrebný na zoradenie zoznamu. Triedenie bublín vyžaduje iba jeden (1) priestor navyše pre dočasnú premennú použitú na zámenu hodnôt. Preto má priestorovú zložitosť O (1).

Zhrnutie

  • Algoritmus triedenia bublín funguje tak, že porovnáva dve susedné hodnoty a zamieňa ich, ak je hodnota vľavo menšia ako hodnota vpravo.
  • Implementácia algoritmu triedenia bublín je v Pythone relatívne jednoduchá. Všetko, čo musíte použiť, je pre slučky a príkazy if.
  • Algoritmus bublinového triedenia rieši problém v tom, že vezme náhodný zoznam položiek a zmení ho na usporiadaný zoznam.
  • Algoritmus triedenia bublín v dátovej štruktúre funguje najlepšie, keď je zoznam už zoradený, pretože vykonáva minimálny počet iterácií.
  • Algoritmus triedenia bubliniek nefunguje dobre, ak je zoznam v opačnom poradí.
  • Bubblerovo triedenie má časovú zložitosť O (n 2 ) a priestorovú zložitosť O (1)
  • Algoritmus bubblerovho triedenia je najvhodnejší na akademické účely a nie na aplikácie v reálnom svete.
  • Optimalizované triedenie bublín zvyšuje efektívnosť algoritmu tým, že pri kontrole hodnôt, ktoré už boli zoradené, preskočí nepotrebné iterácie.