bubble sort c with examples
Technika třídění bublin v C ++.
Bubble Sort je nejjednodušší z technik třídění.
V technice třídění bublin je každý z prvků v seznamu porovnáván s jeho sousedním prvkem. Pokud tedy v seznamu A existuje n prvků, pak je A [0] porovnáno s A [1], A [1] je porovnáno s A [2] atd.
Po porovnání, pokud je první prvek větší než druhý, jsou dva prvky vyměněny.
=> Navštivte zde kompletní kurz C ++ od odborníků.
Co se naučíte:
inicializace statických proměnných c ++
- Technika třídění bublin
- Ilustrace
- Příklad C ++
- Příklad Java
- Analýza složitosti algoritmu třídění bublin
- Závěr
- Doporučené čtení
Technika třídění bublin
Pomocí techniky bublinového třídění se třídění provádí v průchodech nebo iteracích. Na konci každé iterace je tedy nejtěžší prvek umístěn na správné místo v seznamu. Jinými slovy, největší prvek v seznamu bubliny nahoru.
Níže jsme uvedli obecný algoritmus techniky třídění bublin.
Obecný algoritmus
Krok 1 : Pro i = 0 až N-1 opakujte krok 2
Krok 2 : Pro J = i + 1 až N - opakuji
Krok 3 : pokud A [J]> A [i]
Zaměnit A [J] a A [i]
[End of Inner for loop]
[Konec, pokud je vnější pro smyčku]
Krok 4 : Konec
Zde je pseudokód pro algoritmus třídění bublin, kde procházíme seznam pomocí dvou iteračních smyček.
V první smyčce začneme od 0thprvek a v další smyčce začneme od sousedního prvku. V těle vnitřní smyčky porovnáme každý ze sousedních prvků a vyměníme je, pokud nejsou v pořádku. Na konci každé iterace vnější smyčky vybuchne na konci nejtěžší prvek.
Pseudo kód
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array[i-1] > array[i] then swap array[i-1] and array[i] swapped = true end if end for until not swapped end procedure
Výše uvedený je pseudokód pro techniku třídění bublin. Pojďme si nyní ilustrovat tuto techniku pomocí podrobného obrázku.
Ilustrace
Vezmeme pole velikosti 5 a ilustrujeme algoritmus třídění bublin.
Pole zcela roztříděno.
Výše uvedený obrázek lze shrnout do tabulky, jak je uvedeno níže:
Složit | Nezařazený seznam | srovnání | Seřazený seznam |
---|---|---|---|
{5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
1 | {10,5,15,0,12} | {10,5} | {5,10,15,0,12} |
{5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
{5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
{5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
dva | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
{5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
{5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
{5,0,10,12,15} | TŘÍDĚNO |
Jak je znázorněno na obrázku, při každém průchodu se největší prvek probublává až k poslednímu, čímž se seznam při každém průchodu roztřídí. Jak již bylo zmíněno v úvodu, každý prvek je porovnán s přilehlým prvkem a je vzájemně zaměněn, pokud nejsou v pořádku.
Jak je tedy znázorněno na obrázku výše, na konci prvního průchodu, pokud se má pole řadit ve vzestupném pořadí, se největší prvek umístí na konec seznamu. U druhého průchodu je druhý největší prvek umístěn na druhé poslední pozici v seznamu atd.
Když dosáhneme průchodu N-1 (kde N je celkový počet prvků v seznamu), budeme mít celý seznam seřazený.
bezplatná ochrana firewallem pro Windows 10
Techniku třídění bublin lze implementovat v jakémkoli programovacím jazyce. Níže jsme implementovali algoritmus třídění bublin pomocí jazyka C ++ a Java.
Příklad C ++
Podívejme se na příklad programování, abychom demonstrovali třídění bublin.
#include using namespace std; int main () { int i, j,temp,pass=0; int a[10] = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Výstup:
Seznam vstupů…
10 2 0 14 43 25 18 1 5 45
Seznam seřazených prvků ...
0 1 2 5 10 14 18 25 43 45
Počet povolení k seřazení seznamu: 10
Příklad Java
class Main { public static void main(String[] args) { int pass = 0; int[] a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a[i] + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a[i] Výstup:
V obou programech jsme použili řadu 10 prvků a třídili jsme ji pomocí techniky třídění bublin. V obou programech jsme použili dvě smyčky pro iteraci sousedními prvky pole.
nejlepší software pro monitorování teploty CPU a GPU
Na konci každého průchodu (vnější smyčka) je největší prvek v poli probubláván až na konec pole. Počítáme také počet průchodů, které jsou nutné k seřazení celého pole.
Analýza složitosti algoritmu třídění bublin
Z pseudokódu a ilustrace, kterou jsme viděli výše, v bublinovém řazení provádíme srovnání N-1 v prvním průchodu, srovnání N-2 ve druhém průchodu atd.
Celkový počet srovnání v bublinovém řazení je tedy:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-l) / 2
= O (čdva) => Časová složitost techniky třídění bublin
Níže jsou uvedeny různé složitosti techniky třídění bublin:
Nejhorší časová složitost O (n 2) Nejlepší časová složitost Na) Průměrná časová složitost O (n 2) Složitost prostoru O (1)
Technika třídění bublin vyžaduje pouze jeden další paměťový prostor pro dočasnou proměnnou pro usnadnění swapování. Proto je složitost prostoru pro algoritmus třídění bublin O (1).
Všimněte si, že nejlepší časová složitost pro techniku třídění bublin bude, když je seznam již seřazen a bude O (n).
Závěr
Hlavní výhodou Bubble Sort je jednoduchost algoritmu. Při třídění bublin při každém průchodu proběhne největší prvek až na konec seznamu, pokud je pole seřazeno vzestupně.
Podobně pro seřazení seznamu v sestupném pořadí bude nejmenší prvek na svém správném místě na konci každého průchodu.
Jelikož se jedná o nejjednodušší a snadno implementovatelnou techniku třídění, je bublinové třídění obvykle považováno za zavedení třídění publiku. Za druhé, třídění bublin se také používá v aplikacích, jako je počítačová grafika, kde vyplnění hran polygonů atd. Vyžaduje třídění bublin pro třídění vrcholů lemujících polygon.
V našem nadcházejícím výukovém programu se podrobně seznámíme s výběrem řazení.
=> Navštivte zde a dozvíte se C ++ od nuly.
Doporučené čtení