Obsah

• Srovnávací tabulka
• Definice třídění bublin
• Definice třídění výběru
• Závěr

Třídění je jedním z hlavních úkolů v počítačových programech, ve kterých jsou prvky pole uspořádány v určitém konkrétním pořadí. Třídění usnadňuje vyhledávání. Bubble sort and Selection sort jsou algoritmy třídění, které lze rozlišit pomocí metod, které používají pro třídění. Třídění bublin v podstatě vyměňuje prvky, zatímco výběrové řazení provádí třídění výběrem prvku.

Dalším významným rozdílem mezi nimi je, že bublinové řazení je stabilní algoritmus, zatímco výběrové řazení je nestabilní algoritmus. Algoritmus je považován za stabilní prvky se stejným klíčem, které se vyskytují ve stejném pořadí, v jakém se vyskytly před tříděním v seznamu nebo poli. Většina stabilních a nejrychlejších algoritmů obecně používá další paměť.

1. Srovnávací tabulka
2. Definice
3. Klíčové rozdíly
4. Závěr

Srovnávací tabulka

Základ pro srovnání	Třídění bublin	Výběr řazení
Základní	Sousední prvek je porovnán a zaměněn	Největší prvek je vybrán a zaměněn za poslední prvek (v případě vzestupného pořadí).
Nejlepší složitost času případu	Na)	Na2)
Účinnost	Neefektivní	Vylepšená účinnost ve srovnání s bublinovým tříděním
Stabilní	Ano	Ne
Metoda	Výměna	Výběr
Rychlost	Zpomalit	Rychle ve srovnání s bublinkami

Definice třídění bublin

Třídění bublin je nejjednodušší iterační algoritmus, který funguje porovnáním každé položky nebo prvku s položkou vedle ní a jejich výměnou v případě potřeby. Jednoduše řečeno, porovnává první a druhý prvek seznamu a zaměňuje jej, pokud nejsou mimo konkrétní pořadí. Podobně jsou porovnány a zaměněny druhý a třetí prvek a toto srovnání a výměna pokračuje na konec seznamu. Počet srovnání v první iteraci je n-1, kde n je počet prvků v matici. Největší prvek by byl na první pozici po první iteraci. A po každé iteraci počet porovnávání klesá a na poslední iteraci dochází pouze k jednomu porovnání.

Tento algoritmus je nejpomalejším algoritmem třídění. Nejlepší složitost případu (pokud je seznam v pořádku) typu Bubble je řádu n (Na)) a nejhorší složitost je Na²). V nejlepším případě je to řád n, protože pouze porovnává prvky a nezaměňuje je. Tato technika také vyžaduje další prostor pro uložení dočasné proměnné.

Definice třídění výběru

Výběr řazení dosáhl o něco lepšího výkonu a je efektivní než algoritmus třídění bublin. Předpokládejme, že chceme uspořádat pole ve vzestupném pořadí, pak funguje tak, že najdeme největší prvek a vyměníme ho s posledním prvkem a opakujeme následující proces na dílčích polích, dokud nebude celý seznam seřazen.

Při třídění výběru se seřazené a netříděné pole nijak nezmění a spotřebuje řád n² (Na²)) v tom nejlepším i nejhorším případě. Výběr řazení je rychlejší než řazení Bubble.

1. Při třídění bublin je každý prvek a jeho sousední prvek porovnán a v případě potřeby zaměněn. Na druhé straně výběrové řazení funguje tak, že vyberete prvek a zaměníme tento konkrétní prvek za poslední prvek. Vybraný prvek může být největší nebo nejmenší v závislosti na pořadí, tj. Vzestupně nebo sestupně.
2. Nejhorší složitost je u obou algoritmů stejná, tj. O (n²), ale nejlepší složitost je jiná. Řazení bublin trvá řádově n času, zatímco výběr třídění spotřebovává řád n² čas.
3. Bublinové řazení je stabilní algoritmus, naopak výběrové řazení je nestabilní.
4. Algoritmus třídění výběru je rychlý a efektivní ve srovnání s bublinovým tříděním, které je velmi pomalé a neefektivní.

Závěr

Algoritmus řazení bublin je považován za nejjednodušší a nejefektivnější algoritmus, ale algoritmus výběru je účinný ve srovnání s bublinovým tříděním. Třídění bublin také spotřebovává další prostor pro ukládání dočasné proměnné a potřebuje více swapů.