Algoritmus třídění bublin s Pythonem pomocí příkladu seznamu

Obsah:

Anonim

Co je to Bubble Sort?

Bubble Sort je třídicí algoritmus používaný k třídění položek seznamu ve vzestupném pořadí porovnáním dvou sousedních hodnot. Pokud je první hodnota vyšší než druhá hodnota, zaujímá první hodnota pozici druhé hodnoty, zatímco druhá hodnota zaujímá pozici první hodnoty. Pokud je první hodnota nižší než druhá hodnota, nedojde k žádné výměně.

Tento proces se opakuje, dokud nebudou všechny hodnoty v seznamu porovnány a v případě potřeby zaměněny. Každá iterace se obvykle nazývá pass. Počet průchodů v třídění bublin se rovná počtu prvků v seznamu minus jeden.

V tomto výukovém programu Třídění bublin v Pythonu se naučíte:

  • Co je to Bubble Sort?
  • Implementace algoritmu třídění bublin
  • Optimalizovaný algoritmus třídění bublin
  • Vizuální reprezentace
  • Příklady Pythonu
  • Vysvětlení kódu
  • Výhody třídění bublin
  • Nevýhody třídění bublin
  • Analýza složitosti třídění bublin

Implementace algoritmu třídění bublin

Implementaci rozdělíme do tří (3) kroků, konkrétně na problém, řešení a algoritmus, kterým můžeme psát kód pro libovolný jazyk.

Problém

Seznam položek je uveden v náhodném pořadí a rádi bychom je uspořádali uspořádaným způsobem

Zvažte následující seznam:

[21,6,9,33,3]

Řešení

Procházejte seznam porovnáváním dvou sousedních prvků a jejich výměnou, pokud je první hodnota vyšší než druhá hodnota.

Výsledek by měl být následující:

[3,6,9,21,33]

Algoritmus

Algoritmus třídění bublin funguje následovně

Krok 1) Získejte celkový počet prvků. Získejte celkový počet položek v daném seznamu

Krok 2) Určete počet vnějších průchodů (n - 1), které je třeba provést. Jeho délka je seznam minus jedna

Krok 3) Proveďte vnitřní průchody (n - 1) krát pro vnější průchod 1. Získejte hodnotu prvního prvku a porovnejte ji s druhou hodnotou. Pokud je druhá hodnota menší než první hodnota, vyměňte pozice

Krok 4) Opakujte kroky 3, dokud nedosáhnete vnějšího průchodu (n - 1). Získejte další prvek v seznamu a poté opakujte postup, který byl proveden v kroku 3, dokud nebudou všechny hodnoty umístěny ve správném vzestupném pořadí.

Krok 5) Po dokončení všech průchodů výsledek vraťte. Vrátí výsledky seřazeného seznamu

Krok 6) Optimalizujte algoritmus

Pokud jsou seznam nebo sousední hodnoty již seřazeny, vyhněte se zbytečným vnitřním průchodům. Například pokud poskytnutý seznam již obsahuje prvky, které byly seřazeny ve vzestupném pořadí, můžeme smyčku přerušit dříve.

Optimalizovaný algoritmus třídění bublin

Ve výchozím nastavení algoritmus třídění bublin v Pythonu porovnává všechny položky v seznamu bez ohledu na to, zda je seznam již seřazen nebo ne. Pokud je daný seznam již seřazený, je porovnání všech hodnot ztrátou času a prostředků.

Optimalizace třídění bublin nám pomáhá vyhnout se zbytečným iteracím a ušetřit čas a zdroje.

Například pokud jsou první a druhá položka již seřazené, není nutné iterovat zbývající hodnoty. Iterace je ukončena a je zahájena další, dokud není proces dokončen, jak je znázorněno v níže uvedeném příkladu řazení bublin.

Optimalizace se provádí pomocí následujících kroků

Krok 1) Vytvořte proměnnou příznaku, která monitoruje, zda ve vnitřní smyčce došlo k výměně

Krok 2) Pokud hodnoty vyměnily pozice, pokračujte na další iteraci

Krok 3) Pokud výhody nevyměnily pozice, ukončete vnitřní smyčku a pokračujte vnější smyčkou.

Optimalizované třídění bublin je efektivnější, protože provádí pouze nezbytné kroky a přeskočí ty, které nejsou vyžadovány.

Vizuální reprezentace

Vzhledem k seznamu pěti prvků následující obrázky ilustrují, jak třídění bublin iteruje hodnotami při jejich třídění

Následující obrázek ukazuje netříděný seznam

První iterace

Krok 1)

Hodnoty 21 a 6 jsou porovnány s kontrolou, která z nich je větší než druhá.

21 je větší než 6, takže 21 zaujímá pozici obsazenou 6, zatímco 6 zaujímá pozici obsazenou 21

Náš upravený seznam nyní vypadá jako ten výše.

Krok 2)

Hodnoty 21 a 9 jsou porovnány.

21 je větší než 9, takže vyměníme pozice 21 a 9

Nový seznam je nyní uveden výše

Krok 3)

Hodnoty 21 a 33 jsou porovnány, aby byla nalezena větší.

Hodnota 33 je větší než 21, takže nedojde k žádné výměně.

Krok 4)

Hodnoty 33 a 3 jsou porovnány, aby byla nalezena větší.

Hodnota 33 je větší než 3, takže jejich pozice vyměníme.

Seřazený seznam na konci první iterace je jako ten výše

Druhá iterace

Nový seznam po druhé iteraci je následující

Třetí iterace

Nový seznam po třetí iteraci je následující

Čtvrtá iterace

Nový seznam po čtvrté iteraci je následující

Příklady Pythonu

Následující kód ukazuje, jak implementovat algoritmus Bubble Sort v Pythonu.

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)

Provedení výše uvedeného programu třídění bublin v Pythonu přináší následující výsledky

[6, 9, 21, 3, 33]

Vysvětlení kódu

Vysvětlení kódu programu Python Bubble Sort je následující

TADY,

  1. Definuje funkci bubbleSort, která přijímá parametr theSeq. Z kódu nic nevychází.
  2. Získá délku pole a přiřadí hodnotu proměnné n. Z kódu nic nevychází
  3. Spustí smyčku for, která spustí algoritmus třídění bublin (n - 1) krát. Toto je vnější smyčka. Z kódu nic nevychází
  4. Definuje proměnnou příznaku, která se použije k určení, zda došlo k výměně. To je pro účely optimalizace. Z kódu nic nevychází
  5. Spustí vnitřní smyčku, která porovnává všechny hodnoty v seznamu od první po poslední. Z kódu nic nevychází.
  6. Použije příkaz if ke kontrole, zda je hodnota na levé straně větší než hodnota na pravé straně. Z kódu nic nevychází.
  7. Přiřadí hodnotu seq [j] časové proměnné tmp, pokud je podmínka vyhodnocena jako true. Z kódu nic nevychází
  8. Hodnota theSeq [j + 1] je přiřazena pozici theSeq [j]. Z kódu nic nevychází
  9. Hodnota proměnné tmp je přiřazena pozici theSeq [j + 1]. Z kódu nic nevychází
  10. Proměnné příznaku je přiřazena hodnota 1, což znamená, že došlo k výměně. Z kódu nic nevychází
  11. Používá příkaz if ke kontrole, zda je hodnota příznaku proměnné 0. Kód nevydává nic
  12. Pokud je hodnota 0, pak voláme příkaz break, který vykročí z vnitřní smyčky.
  13. Vrátí hodnotu theSeq po jejím seřazení. Výstupem kódu je seřazený seznam.
  14. Definuje proměnnou el, která obsahuje seznam náhodných čísel. Z kódu nic nevychází.
  15. Přiřadí hodnotu funkce bubbleSort k proměnnému výsledku.
  16. Vytiskne hodnotu výsledku proměnné.

Výhody třídění bublin

Následuje několik výhod algoritmu třídění bublin

  • Je snadné to pochopit
  • Funguje velmi dobře, když je seznam již nebo téměř seřazený
  • Nevyžaduje rozsáhlou paměť.
  • Je snadné napsat kód pro algoritmus
  • Prostorové požadavky jsou minimální ve srovnání s jinými třídicími algoritmy.

Nevýhody třídění bublin

Následuje několik nevýhod algoritmu třídění bublin

  • Při řazení velkých seznamů nefunguje dobře. Zabere to příliš mnoho času a zdrojů.
  • Většinou se používá pro akademické účely, a nikoli pro skutečné aplikace.
  • Počet kroků potřebných k seřazení seznamu je řádu n 2

Analýza složitosti třídění bublin

Existují tři typy složitosti:

1) Složitost řazení

Složitost řazení se používá k vyjádření množství časů a prostoru provedení, které je potřeba k seřazení seznamu. Třídění bublin vytváří (n - 1) iterací k seřazení seznamu, kde n je celkový počet prvků v seznamu.

2) Časová složitost

Časová složitost třídění bublin je O (n 2 )

Časovou složitost lze kategorizovat jako:

  • Nejhorší případ - v tomto případě je uvedený seznam sestupně. Algoritmus provádí maximální počet provedení, který je vyjádřen jako [Big-O] O (n 2 )
  • Nejlepší případ - k tomu dojde, když je poskytnutý seznam již seřazen. Algoritmus provádí minimální počet provedení, který je vyjádřen jako [Big-Omega] Ω (n)
  • Průměrný případ - k tomu dojde, když je seznam v náhodném pořadí. Průměrná složitost je vyjádřena jako [Big-theta] ⊝ (n 2 )

3) Složitost prostoru

Složitost prostoru měří množství prostoru navíc, který je potřebný pro řazení seznamu. Třídění bublin vyžaduje pouze jeden (1) prostor navíc pro dočasnou proměnnou použitou pro výměnu hodnot. Proto má prostorovou složitost O (1).

souhrn

  • Algoritmus třídění bublin funguje porovnáním dvou sousedních hodnot a jejich výměnou, pokud je hodnota vlevo menší než hodnota vpravo.
  • Implementace algoritmu třídění bublin je v Pythonu relativně přímočará. Vše, co musíte použít, je pro smyčky a příkazy if.
  • Problém, který algoritmus třídění bublin řeší, je převzetí náhodného seznamu položek a jeho převedení na uspořádaný seznam.
  • Algoritmus třídění bublin v datové struktuře funguje nejlépe, když je seznam již seřazen, protože provádí minimální počet iterací.
  • Algoritmus třídění bublin nefunguje dobře, když je seznam v opačném pořadí.
  • Bubblerův druh má časovou složitost O (n 2 ) a prostorovou složitost O (1)
  • Algoritmus bubblerového řazení je nejvhodnější pro akademické účely a ne pro aplikace v reálném světě.
  • Optimalizované třídění bublin zefektivňuje algoritmus vynecháním zbytečných iterací při kontrole hodnot, které již byly tříděny.