Řazení bublin je považován za jeden z nejjednodušších třídicích algoritmů, který funguje opakovaným zaměňováním sousedních prvků, pokud jsou ve špatném pořadí. S algoritmem třídění bublin uvidíte, že největší prvek (za předpokladu, že řadíme od nejmenších po největší) bude „bublinkovat“ až na začátek seznamu nebo pole.

Příklad:
Předpokládejme, že chceme seřadit seznam nebo pole prvků ve vzestupném pořadí (od nejmenšího po největší): List = (3,1,2)

Protože nedošlo k žádné výměně, říká nám to, že pole je již seřazeno vzestupně!

Nejlepší případ

Nyní zkusme znovu použít stejný algoritmus, ale tentokrát s použitím scénáře nejlepšího případu, kdy jsou prvky již seřazeny v pořadí ( vzestupně) bychom chtěli.

Protože nedošlo k žádné výměně, jsme hotovi a algoritmus provedl pouze 2 srovnání a počet prvků v poli, které budeme nazývat n = 3. Takže vidíme, že pro n prvky, které tento algoritmus v nejlepším případě vezme pouze porovnání n-1, n-1 = O (n)

Postup nebo algoritmus, který jsme použili, je uveden níže:

Tento algoritmus používá příznak zjistit, zda byly prvky vyměněny nebo ne , který umožňuje, aby algoritmus třídění bublin byl v nejlepším případě O (n) místo O (n²) jako jiná implementace třídění bublin.

Výše uvedený algoritmus
Nejhorší případ = O (n²)
Best Case = O (n)

Pojďme se podívat na jinou implementaci algoritmu třídění bublin:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Výše uvedený algoritmus
Nejhorší případ = O (n²)
Nejlepší případ = O (n²)

Nejhorší případ

Pojďme seřadit pole nebo list = (3,2,1), to by byl nejhorší případ, kdy je seznam v úplném opačném pořadí, než jaké si přejeme (ve vzestupném pořadí) pomocí výše uvedeného algoritmu.

První průchod:
(3,2,1) – > Porovnejte prvky 3 & 2
(2,3 , 1) – > Zaměnit 3 & 2 od 2 < 3
( 2,3,1) – > Porovnat prvky 3 & 1
(2,1,3) – > Zaměnit 1 & 3 od 1 < 3

Druhý průchod:
(2,1,3) – > Porovnejte prvky 2 & 1
(1,2,3) – > Zaměnit 2 & 1 od 1 < 2
(1,2,3) – > Porovnejte prvky 2 & 3
(1,2,3) – > od 2 3

Nyní jsme dokončili cyklování skrz obě smyčky, takže pole musí být seřazeno vzestupně.

Všimněte si, že jsme provedli 4 srovnání ve výše uvedeném druhém příkladu a počet prvků v poli budeme nazývat ‚n‘ = 3, takže počet provedených srovnání je (n-1) ² a (n-1) ² = O (n²)

Také skvělá kniha, která vás připraví na rozhovory o programování / programování, se nazývá cracking the coding interview. Pomůže vám seznámit se s algoritmy třídění a řešením problémů, takže si to určitě vyzkoušejte!

Děkujeme za přečtení tohoto článku a doufám, že vám všem pomůže! Pokračujte v učení a pokud chcete více videí s analýzou algoritmů, navštivte a přihlaste se k odběru mých kanálů YouTube (randerson112358 & compsci112358)

Podívejte se na následující více obsahu / videí o analýze a programování algoritmů:

Kanál YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Web:

Video návody k relaci opakování:

Video návody k analýze algoritmů:

Twitter: