BUBBLE SORT - VODIČ ZA DS

U ovom ćemo članku raspravljati o algoritmu Bubble sortiranja. Radni postupak sortiranja mjehurićima je najjednostavniji. Ovaj će članak biti vrlo koristan i zanimljiv studentima jer bi se mogli suočiti s mjehurićima kao pitanjem na ispitima. Dakle, važno je razgovarati o temi.

img css poravnanje

Bubble sortiranje radi na opetovanoj izmjeni susjednih elemenata sve dok nisu u željenom redoslijedu. Naziva se mjehurićima jer je kretanje elemenata niza isto kao kretanje mjehurića zraka u vodi. Mjehurići u vodi dižu se na površinu; slično, elementi niza u mjehurićima se pomiču na kraj u svakoj iteraciji.

Iako je jednostavan za korištenje, prvenstveno se koristi kao obrazovni alat jer je izvedba sortiranja u obliku mjehurića loša u stvarnom svijetu. Nije prikladan za velike skupove podataka. Prosječna i najgora složenost Bubble sortiranja je Na²), gdje n je niz stavki.

Bubble short uglavnom se koristi gdje -

složenost nije važna
poželjan je jednostavan i kratki kod

Algoritam

U algoritmu danom u nastavku, pretpostavimo arr je niz od n elementi. Pretpostavljeno zamijeniti funkcija u algoritmu će zamijeniti vrijednosti zadanih elemenata niza.

 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

Rad algoritma Bubble sort

Sada, da vidimo kako radi algoritam Bubble sortiranja.

Da bismo razumjeli rad algoritma sortiranja u obliku mjehurića, uzmimo nesortirani niz. Uzimamo kratak i precizan niz, jer znamo kakva je složenost sortiranja u mjehurićima Na²).

Neka su elementi niza -

Prvi prolaz

Razvrstavanje će početi od prva dva elementa. Usporedimo ih da provjerimo koji je veći.

Ovdje je 32 veće od 13 (32 > 13), pa je već sortirano. Sada usporedite 32 sa 26.

Ovdje je 26 manje od 36. Dakle, potrebna je zamjena. Nakon izmjene novi niz će izgledati ovako -

Sada usporedite 32 i 35.

Ovdje je 35 veće od 32. Dakle, nije potrebna zamjena jer su već sortirani.

Sada će usporedba biti između 35 i 10.

java concat nizovi

Ovdje je 10 manje od 35 koji nisu sortirani. Dakle, potrebna je zamjena. Sada dolazimo do kraja niza. Nakon prvog prolaza, niz će biti -

Sada prijeđite na drugu iteraciju.

Drugi prolaz

Isti će se postupak slijediti za drugu iteraciju.

Ovdje je 10 manje od 32. Dakle, potrebna je zamjena. Nakon zamjene, niz će biti -

Sada prijeđite na treću iteraciju.

Treći prolaz

Isti će se postupak slijediti za treću iteraciju.

Ovdje je 10 manje od 26. Dakle, potrebna je zamjena. Nakon zamjene, niz će biti -

Sada prijeđite na četvrtu iteraciju.

Četvrti prolaz

Slično, nakon četvrte iteracije, niz će biti -

Dakle, nije potrebna zamjena, tako da je niz potpuno sortiran.

Složenost sortiranja mjehurićima

Pogledajmo sada vremensku složenost sortiranja u obliku mjehurića u najboljem, prosječnom i najgorem slučaju. Također ćemo vidjeti složenost prostora sortiranja mjehurića.

1. Vremenska složenost

Slučaj	Vremenska složenost
Najbolji slučaj	Na)
Prosječan slučaj	Na²)
Najgori slučaj	Na²)

Na).

Na²).

2. Složenost prostora

Složenost prostora	O(1)
Stabilan	DA

Prostorna složenost bubble sortiranja je O(1). To je zato što je u mjehuričastom sortiranju dodatna varijabla potrebna za zamjenu.
Prostorna složenost optimiziranog sortiranja mjehurićima je O(2). To je zato što su dvije dodatne varijable potrebne za optimizirano sortiranje u obliku mjehurića.

Raspravljajmo sada o optimiziranom algoritmu sortiranja mjehurićima.

Optimizirani algoritam sortiranja mjehurićima

U algoritmu za mjehuriće sortiranje, usporedbe se rade čak i kada je niz već sortiran. Zbog toga se vrijeme izvršenja povećava.

Da bismo to riješili, možemo koristiti dodatnu varijablu zamijenjeni. Postavljen je na pravi ako je potrebna zamjena; inače je postavljeno na lažno.

Bit će od pomoći, pretpostavimo da nakon iteracije, ako nije potrebna zamjena, vrijednost varijable zamijenjeni bit će lažno. To znači da su elementi već sortirani i nisu potrebne dodatne iteracije.

Ova metoda će smanjiti vrijeme izvršenja i također optimizirati sortiranje u obliku mjehurića.

Algoritam za optimizirano sortiranje mjehurićima

 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

Implementacija Bubble sortiranja

Pogledajmo sada programe Bubble sortiranja u različitim programskim jezicima.

ssh puni oblik

Program: Napišite program za implementaciju bubble sortiranja u C jeziku.

 #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;>

Izlaz

Program: Napišite program za implementaciju bubble sortiranja u PHP-u.

 <?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;>