Bubble Algoritmus řazení pomocí Python pomocí příkladu seznamu

Co je to Bubble Seřadit?

Bubble Seřadit je třídicí algoritmus používaný k řazení položek seznamu ve vzestupném pořadí porovnáním dvou sousedních hodnot. Pokud je první hodnota vyšší než druhá hodnota, první hodnota zaujme pozici druhé hodnoty, zatímco druhá hodnota zaujme pozici první hodnoty. Pokud je první hodnota nižší než druhá hodnota, neprovádí se žádná záměna.

Tento proces se opakuje, dokud nejsou všechny hodnoty v seznamu porovnány a v případě potřeby zaměněny. Každá iterace se obvykle nazývá průchod. Počet průchodů v bublinovém řazení se rovná počtu prvků v seznamu mínus jeden.

V tomto Bubble Třídění Python konzultace naučíš se:

Provádění Bubble Algoritmus řazení

Implementaci rozdělíme do tří (3) kroků, jmenovitě na problém, řešení a algoritmus, který můžeme použít k psaní kódu pro jakýkoli jazyk.

Problém

Seznam položek je uveden v náhodném pořadí a rádi bychom položky uspořádali

Zvažte následující seznam:

[21,6,9,33,3]

řešení

Iterujte seznamem, porovnejte dva sousední prvky a prohoďte je, 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 bublinového řazení 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é mají být provedeny. Jeho délka je seznam mínus 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í, prohoďte pozice

Krok 4) Opakujte krok 3, dokud nedosáhnete vnějšího průchodu (n – 1). Získejte další prvek v seznamu a poté opakujte proces, 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ů vraťte výsledek. Vraťte výsledky seřazeného seznamu

Krok 6) Optimalizovat algoritmus

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

optimalizovaný Bubble Algoritmus řazení

Ve výchozím nastavení je algoritmus pro řazení bublin Python porovná 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ávání všech hodnot ztrátou času a prostředků.

Optimalizace bublinového řazení nám pomáhá vyhnout se zbytečným iteracím a šetřit čas a zdroje.

Pokud jsou například první a druhá položka již setříděny, není třeba procházet zbývajícími hodnotami. Iterace se ukončí a zahájí se další, dokud není proces dokončen, jak je znázorněno níže Bubble Příklad řazení.

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 nějaké záměně

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

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

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

Vizuální reprezentace

Vzhledem k tomu, že je uveden seznam pěti prvků, následující obrázky ilustrují, jak bublinové řazení iteruje přes hodnoty při jejich řazení

Následující obrázek ukazuje neseřazený seznam

První iterace

Krok 1)

Hodnoty 21 a 6 se porovnají, aby se zjistilo, 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, která byla obsazena 21

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

Krok 2)

Hodnoty 21 a 9 jsou porovnány.

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

Nový seznam je nyní jako 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 k žádné záměně nedochází.

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 prohodí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í

Python Příklady

Následující kód ukazuje, jak implementovat Bubble Algoritmus řazení v 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)

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

[6, 9, 21, 3, 33]

Vysvětlení kódu

Vysvětlení pro Python Bubble Kód třídění programu je následující

TADY,

Definuje funkci bubbleSort, která přijímá parametr theSeq. Kód nevypisuje nic.
Získá délku pole a přiřadí hodnotu proměnné n. Kód nevypisuje nic
Spustí cyklus for, který spustí algoritmus řazení podle bublin (n – 1) krát. Toto je vnější smyčka. Kód nevypisuje nic
Definuje proměnnou příznaku, která bude použita k určení, zda došlo k záměně nebo ne. Toto je pro účely optimalizace. Kód nevypisuje nic
Spustí vnitřní smyčku, která porovná všechny hodnoty v seznamu od první po poslední. Kód nevypisuje nic.
Používá příkaz if ke kontrole, zda je hodnota na levé straně větší než hodnota na pravé straně. Kód nevypisuje nic.
Přiřadí hodnotu Seq[j] časové proměnné tmp, pokud se podmínka vyhodnotí jako pravdivá. Kód nevypisuje nic
Hodnota Seq[j + 1] je přiřazena pozici Seq[j]. Kód nevypisuje nic
Hodnota proměnné tmp je přiřazena k pozici Seq[j + 1]. Kód nevypisuje nic
Příznakové proměnné je přiřazena hodnota 1, která označuje, že došlo k výměně. Kód nevypisuje nic
Používá příkaz if ke kontrole, zda je hodnota parametru proměnné 0. Kód nevypisuje nic
Pokud je hodnota 0, pak zavoláme příkaz break, který vystoupí z vnitřní smyčky.
Po seřazení vrátí hodnotu Seq. Výstupem kódu je seřazený seznam.
Definuje proměnnou el, která obsahuje seznam náhodných čísel. Kód nevypisuje nic.
Přiřadí hodnotu funkce bubbleSort proměnnému výsledku.
Vytiskne hodnotu výsledku proměnné.

Bubblvýhody řazení

Následují některé z výhod algoritmu řazení 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é nároky jsou minimální ve srovnání s jinými třídicími algoritmy.

Bubble sort Nevýhody

Následují některé z nevýhod algoritmu pro třídění bublin

Při řazení velkých seznamů nefunguje dobře. Vyžaduje to příliš mnoho času a prostředků.
Většinou se používá pro akademické účely a ne pro aplikace v reálném světě.
Počet kroků potřebných k seřazení seznamu je v pořadí n²

Analýza složitosti Bubble Seřadit

Existují tři typy složitosti:

1) Řazení složitosti

Složitost řazení se používá k vyjádření doby provádění a prostoru, který je zapotřebí k seřazení seznamu. Bublinové řazení provádí (n – 1) iterací pro seřazení seznamu, kde n je celkový počet prvků v seznamu.

2) Časová složitost

Časová složitost bublinového řazení je O(n²)

Časovou složitost lze rozdělit do následujících kategorií:

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

3) Prostorová složitost

Prostorová složitost udává množství místa navíc, které je potřeba k seřazení seznamu. Bublinové řazení vyžaduje pouze jednu (1) mezeru navíc pro dočasnou proměnnou používanou k výměně hodnot. Má tedy prostorovou složitost O (1).

Shrnutí

Algoritmus řazení podle bublin funguje tak, že porovnává dvě sousední hodnoty a prohodí je, pokud je hodnota vlevo menší než hodnota vpravo.
Implementace algoritmu pro třídění bublin je relativně přímočará Python. Vše, co potřebujete, jsou pro cykly a příkazy if.
Problém, který algoritmus pro řazení bublin řeší, je vzít náhodný seznam položek a převést jej na uspořádaný seznam.
Algoritmus bublinového řazení v datové struktuře funguje nejlépe, když je seznam již seřazen, protože provádí minimální počet iterací.
Algoritmus řazení podle bublin nefunguje dobře, když je seznam v obráceném pořadí.
Bublinové řazení má časovou složitost O (n²) a prostorová složitost O (1)
Algoritmus třídění bubbler se nejlépe hodí pro akademické účely a ne pro aplikace v reálném světě.
Optimalizované bublinové řazení zefektivňuje algoritmus tím, že vynechává zbytečné iterace při kontrole hodnot, které již byly seřazeny.