Řazení bublin v Pythonu - Vysvětlení řazení bublin pomocí ukázkového kódu

Úvod do třídění bublin v Pythonu

Bubble sort je jednoduchý a logický třídicí algoritmus. Jeho pracovní princip je založen na rekurzivním zaměňování sousedních prvků, pokud je objednávka nesprávná. V tomto tématu se budeme učit o Bubble Sort in Python.

Bubble sort někdy také označované jako Sinking sort, Ripple sort.

Podívejme se na příklad:

První běh

( 6 1 4 3) -> ( 1 6 4 2): Zde jsou ^první dva prvky zaměněny, pokud není objednávka správná.

(1 6 4 2) -> (1 4 6 2): Zde jsou další dva prvky zaměněny, pokud není objednávka správná.

(1 4 6 2 ) -> (1 4 2 6 ): Zde jsou další dva prvky zaměněny, pokud není objednávka správná.

Druhý běh

( 1 4 2 6) -> ( 1 4 2 6): Zde se porovnávají ^první dva prvky, ale nevyměnily se, protože pořadí je správné.

(1 4 2 6) -> (1 2 4 6): Zde se zaměňují další dva prvky, protože pořadí nebylo správné.

(1 2 4 6 ) -> (1 2 4 6 ): Zde se porovnávají poslední dva prvky, ale nevyměnily se tak, jak je pořadí

Teď víme, že pole vypadá roztříštěné, ale jeden běh je vyžadován bez swapu, aby algoritmus věděl, zda je třídění provedeno.

Třetí běh

( 1 2 4 6) -> ( 1 2 4 6): Ve dvou prvcích nelze zaměnit.

(1 2 4 6) -> (1 2 4 6): V dalších dvou prvcích není zaměněna.

(1 2 4 6 ) -> (1 2 4 6 ): Žádný swap v posledních dvou prvcích.

Protože v žádné fázi nedošlo k žádným swapům, algoritmus chápe, že řazení je perfektní.

Řazení bublin má své jméno, protože prvky se pohybují nahoru do správného pořadí, které je jako bubliny stoupající na povrch.

Řazení bublin v jazyce Python

Nyní se podívejme na logickou implementaci třídění bublin přes python. Python je dnes velmi rozšířeným jazykem. Pochopení pomocí pythonu vám jistě dá jistotu, že budete moci psát i v jiných jazycích.

Pythonův kód

def bubble_Sort(arr): m = len(arr) # Traverse through all the array elements for u in range(m): for v in range(0, mu-1): # traverse the array from 0 to mu-1 # Swap if the element is greater than adjacent next one if arr(v) > arr(v+1) : arr(v), arr(v+1) = arr(v+1), arr(v)

K tisku pole po bublinovém třídění potřebujete následující kód:

for i in range(len(arr)): print("%d" %arr(i)), Here arr will be your array.

Vysvětlení kódu Python

Zde „m“ je délka pole. Dvě pro smyčky drží skutečnou pozemní logiku, kde „u“ představuje první prvek, zatímco „v“ představuje druhý, s nímž se první prvek musí porovnat pro výměnu, pokud není pořadí řazení mezi oběma nesprávné.

„Arr (v)> arr (v + 1)“ představuje porovnání po sobě jdoucích prvků, pokud je první prvek větší než druhý prvek, výměnná operace bude provedena následujícím výrazem:

To je „arr (v), arr (v + 1) = arr (v + 1), arr (v)“.

Tato výměna se nazývá swap. Dobrou součástí je, že pro tento druh swapové operace není nutná dočasná paměť.

„U“ představuje smyčku každého cyklu, zatímco „v“ představuje fáze každé fáze. Lze uvést příklad ve výše uvedené části.

Po provedení třídění bublin můžete vidět seřazené pole s níže uvedeným kódem:

for i in range(len(arr)): print ("%d" %arr(i)),

Podívejme se, jak se to v Pythonu IDE chová, pro hlubší pochopení:

Výstup:

Existuje několik faktů o Bubble Sort, které by měli všichni vědět před implementací:

Bublinový druh je často považován za nevhodnou efektivní metodu třídění. Protože musí vyměňovat položky, dokud není známo její konečné umístění. To vše vede k plýtvání provozem, a tedy velmi nákladné. Tento algoritmus prochází každým prvkem, pokud je třídění vyžadováno nebo není vyžadováno. Jakmile běh proběhne bez výměny, je řazení bublin považováno za dokončené.
Toto je nejjednodušší ze všech datových struktur, pro každého začátečníka to dává dobrou důvěru. Je snadné jej sestavit a pochopit.
Využívá spoustu času a paměti.
Toto je považováno za stabilní algoritmus, protože zachovává relativní pořadí prvků.
Považováno za dobré pro malé pole / seznam. Nicméně, je to špatný nápad používat ho pro dlouhé.

Závěr

Při procházení výše uvedeným obsahem bublinového třídění bylo možné získat krystalicky jasné porozumění tomuto třídicímu algoritmu, specializovanému na python. Jakmile si člověk osvojí logiku bublinového třídění, porozumění druhé sadě datových struktur bude jednodušší. Logický přístup je jediný způsob, jak vyniknout v oblasti datové struktury. Pochopit nejprve logiku algoritmu datové struktury v každé fázi a poté zacílit jeho kód pomocí Pythonu nebo v jakémkoli jiném jazyce.

Doporučené články

Toto je průvodce pro třídění bublin v Pythonu. Zde diskutujeme logickou implementaci třídění bublin pomocí pythonového kódu s vysvětlením. Další informace naleznete také v následujícím článku -