Zoradenie bublín v Pythone Vysvetlenie triedenia bubliniek pomocou vzorového kódu

Úvod do triedenia bubliniek v Pythone

Bubble sort je jednoduchý a logický algoritmus triedenia. Jeho pracovný princíp je založený na rekurzívnom zamieňaní susedných prvkov, ak je objednávka nesprávna. V tejto téme sa dozvieme viac o triedení bublín v Pythone.

Bubble sort niekedy nazývané aj Sinking sort, Ripple sort.

Pozrime sa na príklad:

Prvý beh

( 6 1 4 3) -> ( 1 6 4 2): V tomto prípade sú ^1. dva prvky zamenené, ak nie je poradie správne.

(1 6 4 2) -> (1 4 6 2): Tu sú ďalšie dva prvky zamenené, ak nie je poradie správne.

(1 4 6 2 ) -> (1 4 2 6 ): V prípade nesprávneho poradia sa tu zamenia ďalšie dva prvky.

Druhý beh

( 1 4 2 6) -> ( 1 4 2 6): Tu sa porovnávajú ^1. dva prvky, ale nevymieňajú sa, pretože poradie je správne.

(1 4 2 6) -> (1 2 4 6): Tu sa vymenia ďalšie dva prvky, pretože poradie nebolo správne.

(1 2 4 6 ) -> (1 2 4 6 ): Tu sa porovnávajú posledné dva prvky, ale nevymenili sa tak, ako je poradie

Teraz vieme, že pole vyzerá zoradené, ale je potrebný jeden chod bez výmeny, aby algoritmus vedel, či je triedenie dokončené.

Tretí beh

( 1 2 4 6) -> ( 1 2 4 6): Žiadne dva prvky sa nevymieňajú.

(1 2 4 6) -> (1 2 4 6): Žiadne ďalšie prvky sa nevymieňajú.

(1 2 4 6 ) -> (1 2 4 6 ): Posledné dva prvky sa nevymieňajú.

Pretože v žiadnej fáze nedošlo k žiadnym swapom, algoritmus teraz chápe, že triedenie je dokonalé.

Bublina má svoje meno, pretože prvky sa pohybujú hore v správnom poradí, ktoré je ako bubliny stúpajúce k povrchu.

Zoradenie bublín v jazyku Python

Teraz sa pozrime na logickú implementáciu triedenia bublín cez python. Python je v súčasnosti veľmi rozšíreným jazykom. Pochopenie pomocou Pythonu vám určite dá istotu, že budete môcť písať aj v iných jazykoch.

Pythonov 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)

Ak chcete tlačiť pole po triedení bubliniek, potrebujete nasledujúci kód:

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

Vysvetlenie kódu Python

„M“ je dĺžka poľa. Dve pre slučky držia skutočnú pozemnú logiku, kde „u“ predstavuje prvý prvok, zatiaľ čo „v“ predstavuje druhý, s ktorým sa musí prvý prvok porovnávať na účely výmeny, ak nie je poradie zoradenia medzi obidvomi správne.

„Arr (v)> arr (v + 1)“ predstavuje porovnanie po sebe nasledujúcich prvkov, ak je prvý prvok väčší ako druhý prvok, výmenná operácia sa vykoná nasledujúcim výrazom:

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

Táto výmena sa nazýva swap. Dobrá časť je, že na tento druh operácie výmeny nie je potrebná dočasná pamäť.

„U“ predstavuje slučku každého cyklu, zatiaľ čo „v“ predstavuje fázy každej fázy. Možno uviesť príklad z vyššie uvedenej časti.

Po vykonaní triedenia bubliniek je možné vidieť zoradené pole s kódom uvedeným nižšie:

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

Pozrime sa, ako sa to v Python IDE chová, aby sme lepšie porozumeli:

Výkon:

Existuje niekoľko faktov o triedení bublín, ktoré by mali všetci vedieť pred implementáciou:

Bublina je často považovaná za nevhodnú metódu triedenia. Pretože musí vymieňať položky, kým nie je známe ich konečné umiestnenie. To všetko vedie k plytvaniu operáciami, a preto je veľmi nákladné. Tento algoritmus prechádza cez každý prvok, ak je triedenie požadované alebo nepožadované. Akonáhle priebeh prejde bez výmeny, druh bubliny sa považuje za dokončený.
Toto je najjednoduchšie zo všetkých dátových štruktúr, pre každého začiatočníka to dáva dobrú dôveru. Konštrukcia a porozumenie je ľahké.
Využíva veľa času a pamäte.
Toto sa považuje za stabilný algoritmus, pretože zachováva relatívne poradie prvkov.
Považované za dobré pre malé pole / zoznam. Je to však zlý nápad používať ho na dlhé roky.

záver

Pri prechádzaní vyššie uvedeným obsahom bublinového triedenia by sa dalo získať krištáľovo jasné porozumenie tohto triediaceho algoritmu, ktorý sa špecializoval na python. Akonáhle sa človek osvojí s logikou bublinového triedenia, porozumenie druhej skupine dátových štruktúr bude potom jednoduchšie. Logický prístup je jediný spôsob, ako vyniknúť v oblasti štruktúry údajov. Pochopiť najprv logiku algoritmu dátovej štruktúry v každej fáze a potom zacieľovať jeho kód cez Python alebo v akomkoľvek inom jazyku.

Odporúčané články

Toto je sprievodca triedením bubliniek v Pythone. Tu diskutujeme o logickej implementácii triedenia bublín pomocou pythonového kódu s vysvetlením. Viac informácií nájdete aj v nasledujúcom článku -