BUBLINOVÉ TRIEDENIE

V tomto článku budeme diskutovať o algoritme Bubble sort. Pracovný postup bublinkového triedenia je najjednoduchší. Tento článok bude pre študentov veľmi užitočný a zaujímavý, pretože pri skúškach môžu čeliť bublinovému triedeniu ako otázke. Preto je dôležité diskutovať o téme.

fmoviez

Bublinové triedenie funguje na opakovanom zamieňaní susedných prvkov, kým nie sú v zamýšľanom poradí. Nazýva sa to bublinové triedenie, pretože pohyb prvkov poľa je rovnaký ako pohyb vzduchových bublín vo vode. Bubliny vo vode stúpajú na povrch; podobne sa prvky poľa v bublinovom triedení presúvajú na koniec v každej iterácii.

Hoci sa používa jednoducho, používa sa predovšetkým ako vzdelávací nástroj, pretože výkonnosť bublinového triedenia je v reálnom svete nízka. Nie je vhodný pre veľké súbory údajov. Priemerná a najhoršia zložitosť Bubble sort je O(n²), kde n je množstvo položiek.

Bubble short sa používa hlavne tam, kde -

na zložitosti nezáleží
preferuje sa jednoduchý a krátky kód

Algoritmus

V algoritme uvedenom nižšie predpokladajme arr je rad n prvkov. Predpokladané vymeniť funkcia v algoritme zamení hodnoty daných prvkov poľa.

 begin BubbleSort(arr) for all array elements if arr[i] &gt; arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort

Fungovanie algoritmu Bubble sort

Teraz sa pozrime na fungovanie algoritmu Bubble sort.

Aby sme pochopili fungovanie algoritmu triedenia bublín, zoberme si netriedené pole. Berieme krátke a presné pole, pretože vieme, že zložitosť bublinového triedenia je O(n²).

Nech sú prvky poľa -

Prvý prechod

Triedenie začne od prvých dvoch prvkov. Porovnajte ich, aby ste zistili, čo je väčšie.

Tu je 32 väčšie ako 13 (32 > 13), takže je už zoradené. Teraz porovnajte 32 s 26.

Tu je 26 menšie ako 36. Preto je potrebná výmena. Po výmene bude nové pole vyzerať takto -

Teraz porovnajte 32 a 35.

Tu je 35 väčšie ako 32. Takže nie je potrebná žiadna výmena, pretože sú už zoradené.

Teraz bude porovnanie medzi 35 a 10.

Tu je 10 menšie ako 35, ktoré nie sú zoradené. Preto je potrebná výmena. Teraz sa dostávame na koniec poľa. Po prvom prechode bude pole -

Teraz prejdite na druhú iteráciu.

Druhý prechod

Rovnaký proces bude nasledovať pri druhej iterácii.

rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom

Tu je 10 menšie ako 32. Preto je potrebná výmena. Po výmene bude pole -

Teraz prejdite na tretiu iteráciu.

Tretí prechod

Rovnaký proces bude nasledovať pri tretej iterácii.

Tu je 10 menšie ako 26. Preto je potrebná výmena. Po výmene bude pole -

Teraz prejdite na štvrtú iteráciu.

Štvrtý prechod

Podobne po štvrtej iterácii bude pole -

Preto nie je potrebná žiadna výmena, takže pole je úplne zoradené.

Zložitosť triedenia bublín

Teraz sa pozrime na časovú zložitosť triedenia bublín v najlepšom prípade, priemernom prípade a najhoršom prípade. Uvidíme aj priestorovú zložitosť bublinkového triedenia.

1. Časová zložitosť

Prípad	Časová zložitosť
Najlepší prípad	O(n)
Priemerný prípad	O(n²)
V najhoršom prípade	O(n²)

O(n).

O(n²).

2. Zložitosť priestoru

Priestorová zložitosť	O(1)
Stabilný	ÁNO

Priestorová zložitosť bublinového triedenia je O(1). Je to preto, že pri bublinovom triedení je na výmenu potrebná ďalšia premenná.
Priestorová zložitosť optimalizovaného triedenia bublín je O(2). Je to preto, že pri optimalizovanom triedení bublín sú potrebné dve premenné navyše.

Teraz poďme diskutovať o optimalizovanom algoritme triedenia bublín.

Optimalizovaný algoritmus bublinového triedenia

V algoritme bublinového triedenia sa porovnávania vykonávajú aj vtedy, keď je pole už zoradené. Z tohto dôvodu sa čas vykonávania predlžuje.

Aby sme to vyriešili, môžeme použiť extra premennú vymenené. Je nastavený na pravda ak si výmena vyžaduje; inak je nastavený na falošný.

Bude užitočné, ako predpokladajme, že po iterácii, ak nie je potrebná výmena, bude hodnota premennej vymenené bude falošný. Znamená to, že prvky sú už zoradené a nie sú potrebné žiadne ďalšie iterácie.

Táto metóda skráti čas vykonania a tiež optimalizuje triedenie bublín.

Algoritmus pre optimalizované triedenie bublín

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] &gt; array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort

Implementácia Bubble sort

Teraz sa pozrime na programy Bubble sort v rôznych programovacích jazykoch.

np nuly

Program: Napíšte program na implementáciu triedenia bublín v jazyku C.

 #include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are - 
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are - 
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
 before sorting array elements are - 
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>&apos;); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - &apos; + &apos; <br>&apos;); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;>

Výkon

Program: Napíšte program na implementáciu triedenia bublín v PHP.

 <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;>