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 procedureVýš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í
