bubble sort c with examples
Technika triedenia bublín v C ++.
Bubble Sort je najjednoduchšia z triediacich techník.
V technike bublinového triedenia sa každý z prvkov v zozname porovnáva s jeho susedným prvkom. Ak teda v zozname A existuje n prvkov, potom sa porovnáva A (0) s A (1), A (1) sa porovnáva s A (2) atď.
Po porovnaní, ak je prvý prvok väčší ako druhý, sa tieto dva prvky zamenia.
=> Navštívte tu kompletný kurz C ++ od odborníkov.
Čo sa dozviete:
Ako otvorím súbor APK
- Technika triedenia bublín
- Ilustrácia
- Príklad C ++
- Príklad Java
- Analýza zložitosti algoritmu triedenia bublín
- Záver
- Odporúčané čítanie
Technika triedenia bublín
Pomocou techniky bublinového triedenia sa triedenie vykonáva v priechodoch alebo iteráciách. Na konci každej iterácie sa teda najťažší prvok umiestni na správne miesto v zozname. Inými slovami, najväčší prvok v zozname prebubláva.
Ďalej sme uviedli všeobecný algoritmus techniky triedenia bublín.
Všeobecný algoritmus
Krok 1 : Pre i = 0 až N-1 opakujte krok 2
Krok 2 : Pre J = i + 1 až N - opakujem
Krok 3 : ak A (J)> A (i)
Zamieňajte A (J) a A (i)
(Koniec vnútornej strany pre slučku)
(Koniec, ak je vonkajší pre slučku)
Krok 4 : Východ
Tu je pseudokód pre algoritmus triedenia bublín, kde prechádzame zoznam pomocou dvoch iteračných slučiek.
V prvej slučke začneme od nulythprvku a v ďalšej slučke vychádzame zo susedného prvku. V tele vnútornej slučky porovnáme každý zo susedných prvkov a zameníme ich, ak nie sú v poriadku. Na konci každej iterácie vonkajšej slučky na konci prebubláva najťažší prvok.
Pseudokó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
Vyššie uvedený je pseudokód pre techniku bublinového triedenia. Poďme si teraz ilustrovať túto techniku pomocou podrobnej ilustrácie.
Ilustrácia
Vezmeme pole s veľkosťou 5 a ilustrujeme algoritmus bublinového triedenia.
Pole je úplne zoradené.
Vyššie uvedenú ilustráciu je možné zhrnúť do tabuľky, ako je uvedené nižšie:
Prejdite | Netriedený zoznam | porovnanie | Zoradený zoznam |
---|---|---|---|
{5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
jeden | {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,012,15} | |
dva | {5,10,012,15} | {5,10} | {5,10,012,15} |
{5,10,012,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} | Triedené |
Ako je znázornené na ilustrácii, pri každom prechode prebubláva najväčší prvok až po posledný, čím sa zoznam roztriedi pri každom prechode. Ako bolo spomenuté v úvode, každý prvok sa porovnáva s jeho susedným prvkom a navzájom sa zamieňajú, ak nie sú v poriadku.
Ako je teda znázornené na ilustrácii vyššie, na konci prvého prechodu, ak sa má pole zoradiť vzostupne, sa najväčší prvok umiestni na koniec zoznamu. Pri druhom prechode sa druhý najväčší prvok umiestni na druhú poslednú pozíciu v zozname atď.
Keď dosiahneme priechod N-1 (kde N je celkový počet prvkov v zozname), budeme mať celý zoznam zoradený.
kde nájdem kľúč zabezpečenia siete na mojom smerovači
Techniku bublinového triedenia je možné implementovať v ktoromkoľvek programovacom jazyku. Nižšie sme implementovali algoritmus triedenia bublín pomocou jazyka C ++ a Java.
Príklad C ++
Pozrime sa na príklad programovania, ktorý demonštruje triedenie bublín.
#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ýkon:
Zoznam vstupov ...
10 2 0 14 43 25 18 1 5 45
Zoznam zoradených prvkov ...
0 1 2 5 10 14 18 25 43 45
Počet povolení na triedenie zoznamu: 10
Prí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ýkon:

V obidvoch programoch sme použili pole 10 prvkov a triedili sme ho pomocou techniky bublinového triedenia. V obidvoch programoch sme použili dve cykly for na iteráciu cez susedné prvky poľa.
Na konci každého prechodu (vonkajšia slučka) je najväčší prvok v poli prebublávaný až na koniec poľa. Počítame tiež počet prechodov, ktoré sú potrebné na zoradenie celého poľa.
Analýza zložitosti algoritmu triedenia bublín
Z pseudokódu a ilustrácie, ktorú sme videli vyššie, pri bublinovom triedení robíme porovnania N-1 pri prvom prechode, porovnania N-2 pri druhom prechode atď.
Preto je celkový počet porovnaní v bublinovom triedení:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-l) / 2
= O (ndva) => Časová zložitosť techniky triedenia bublín
Ďalej sú uvedené rôzne zložitosti techniky triedenia bublín:
ako vytvoriť nový zoznam v
Najhoršia časová zložitosť O (n 2) Najlepšia časová zložitosť prípadu O (n) Priemerná časová zložitosť O (n 2) Zložitosť priestoru O (1)
Technika triedenia bublín vyžaduje na uľahčenie výmeny iba jeden ďalší pamäťový priestor pre dočasnú premennú. Z tohto dôvodu je priestorová zložitosť pre algoritmus triedenia bublín O (1).
Upozorňujeme, že najlepšia časová zložitosť pre techniku bublinového triedenia bude, keď je zoznam už zoradený a bude O (n).
Záver
Hlavnou výhodou Bubble Sort je jednoduchosť algoritmu. Pri triedení podľa bubliniek pri každom prechode najväčší prvok prebubláva až na koniec zoznamu, ak je pole zoradené vzostupne.
Podobne, aby bol zoznam zoradený zostupne, bude najmenší prvok na konci každého prechodu na správnom mieste.
Ako najjednoduchšia a ľahko implementovateľná technika triedenia sa bublinkové triedenie zvyčajne používa na zoznámenie publika s publikom. Po druhé, triedenie bublín sa používa aj v aplikáciách ako počítačová grafika, kde vyplnenie hrán polygónu atď. Vyžaduje triedenie bublín na triedenie vrcholov lemujúcich polygón.
V našom pripravovanom výučbe sa podrobne dozvieme o triedení výberu.
=> Navštívte tu a dozviete sa C ++ od nuly.
Odporúčané čítanie
- Shell zoradený v C ++ s príkladmi
- Výber Zoradiť v C ++ s príkladmi
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Zoradenie vloženia v C ++ s príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Hromadné triedenie v C ++ s príkladmi
- Rýchle triedenie v C ++ s príkladmi