BUBLINOVÉ ŘAZENÍ

V tomto článku budeme diskutovat o algoritmu Bubble sort. Pracovní postup bublinkového třídění je nejjednodušší. Tento článek bude pro studenty velmi užitečný a zajímavý, protože při zkouškách mohou čelit bublinovému třídění jako otázce. Je tedy důležité o tématu diskutovat.

státy v USA

Bublinové třídění funguje na opakovaném přehazování sousedních prvků, dokud nejsou v zamýšleném pořadí. Říká se tomu bublinové třídění, protože pohyb prvků pole je stejný jako pohyb vzduchových bublin ve vodě. Bubliny ve vodě stoupají k hladině; podobně se prvky pole v bublinovém řazení v každé iteraci přesunou na konec.

Přestože se snadno používá, používá se především jako vzdělávací nástroj, protože výkonnost bublinového třídění je v reálném světě špatná. Není vhodný pro velké soubory dat. Průměrná a nejhorší složitost Bubble sort je Na²), kde n je řada položek.

Bubble short se používá hlavně tam, kde -

na složitosti nezáleží
preferuje se jednoduchý a krátký kód

Algoritmus

V níže uvedeném algoritmu předpokládejme arr je pole n Prvky. Předpokládané vyměnit funkce v algoritmu prohodí hodnoty daných prvků pole.

 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

Fungování algoritmu Bubble sort

Nyní se podívejme, jak funguje algoritmus Bubble sort.

Abychom porozuměli fungování algoritmu řazení bublin, vezměme si netříděné pole. Bereme krátké a přesné pole, jak víme, složitost bublinového třídění je Na²).

Nechť prvky pole jsou -

První průchod

Třídění začne od prvních dvou prvků. Porovnejte je, abyste zjistili, která je větší.

Zde je 32 větší než 13 (32 > 13), takže je již seřazeno. Nyní porovnejte 32 s 26.

Zde je 26 menší než 36. Je tedy nutná výměna. Po výměně bude nové pole vypadat takto -

Nyní porovnejte 32 a 35.

Zde je 35 větší než 32. Není tedy vyžadována žádná výměna, protože jsou již seřazeny.

Nyní bude srovnání mezi 35 a 10.

Zde je 10 menší než 35, které nejsou seřazeny. Výměna je tedy nutná. Nyní se dostáváme na konec pole. Po prvním průchodu bude pole -

Nyní přejděte k druhé iteraci.

Druhý průchod

Stejný proces bude následovat pro druhou iteraci.

Zde je 10 menší než 32. Je tedy nutná výměna. Po výměně bude pole -

Nyní přejděte ke třetí iteraci.

Třetí průchod

Stejný proces bude následovat pro třetí iteraci.

Intellij idea vs eclipse

Zde je 10 menší než 26. Je tedy nutná výměna. Po výměně bude pole -

Nyní přejděte ke čtvrté iteraci.

Čtvrtý průchod

Podobně po čtvrté iteraci bude pole -

Není tedy vyžadována žádná výměna, takže pole je kompletně seřazeno.

Složitost řazení bublin

Nyní se podívejme na časovou složitost bublinového řazení v nejlepším případě, průměrném případě a nejhorším případě. Uvidíme také prostorovou složitost bublinového třídění.

1. Časová složitost

Pouzdro	Časová složitost
Nejlepší případ	Na)
Průměrný případ	Na²)
Nejhorší případ	Na²)

Na).

Na²).

2. Prostorová složitost

Vesmírná složitost	O(1)
Stabilní	ANO

Prostorová složitost bublinového třídění je O(1). Je to proto, že v bublinovém třídění je pro swapování vyžadována další proměnná.
Prostorová složitost optimalizovaného třídění bublin je O(2). Je to proto, že v optimalizovaném třídění bublin jsou vyžadovány dvě další proměnné.

Nyní pojďme diskutovat o optimalizovaném algoritmu třídění bublin.

Optimalizovaný algoritmus pro třídění podle bublin

V algoritmu bublinového třídění se porovnání provádějí, i když je pole již seřazeno. Kvůli tomu se prodlužuje doba realizace.

K jeho vyřešení můžeme použít proměnnou navíc vyměněno. Je nastaveno na skutečný pokud výměna vyžaduje; jinak je nastaveno na Nepravdivé.

Bude užitečné, jako předpokládejme, že po iteraci, pokud není vyžadována žádná výměna, bude hodnota proměnné vyměněno bude Nepravdivé. To znamená, že prvky jsou již setříděny a nejsou nutné žádné další iterace.

Tato metoda zkrátí dobu provádění a také optimalizuje třídění bublin.

Algoritmus pro optimalizované třídění bublin

 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

Implementace Bubble sort

Nyní se podívejme na programy Bubble sort v různých programovacích jazycích.

np nuly

Program: Napište program pro implementaci třídění bublin v jazyce 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ýstup

Program: Napište program pro implementaci třídění bublin 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;>