BUBBLE SORT - VADNICA ZA DS

V tem članku bomo obravnavali algoritem Bubble sort. Delovni postopek sortiranja z mehurčki je najenostavnejši. Ta članek bo študentom zelo koristen in zanimiv, saj se bodo morda soočili z razvrščanjem v mehurčkih kot vprašanjem pri izpitih. Zato je pomembno razpravljati o temi.

operacijski sistemi mac

Razvrščanje z mehurčki deluje na večkratni zamenjavi sosednjih elementov, dokler niso v želenem vrstnem redu. Imenuje se mehurčkasto razvrščanje, ker je gibanje elementov niza podobno gibanju zračnih mehurčkov v vodi. Mehurčki v vodi se dvignejo na površje; podobno se elementi matrike pri mehurčkovem razvrščanju premaknejo na konec v vsaki ponovitvi.

Čeprav je preprost za uporabo, se uporablja predvsem kot izobraževalno orodje, ker je zmogljivost mehurčkov v resničnem svetu slaba. Ni primeren za velike nabore podatkov. Povprečna in najslabša zapletenost Bubble sort je O(n²), kje n je več predmetov.

Bubble short se večinoma uporablja tam, kjer -

kompleksnost ni pomembna
prednostna je preprosta in kratka koda

Algoritem

V spodnjem algoritmu predpostavimo prir je niz n elementi. Predpostavljeno zamenjava funkcija v algoritmu bo zamenjala vrednosti danih elementov polja.

 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

Delovanje algoritma Bubble sort

Zdaj pa si oglejmo delovanje algoritma Bubble sort.

Da bi razumeli delovanje algoritma za razvrščanje z mehurčki, vzemimo nerazvrščeno matriko. Vzamemo kratko in natančno matriko, saj vemo, kako zapletena je mehurčkasta sorta O(n²).

Naj so elementi matrike -

Prvi prehod

Razvrščanje se bo začelo od prvih dveh elementov. Primerjajmo jih, da preverimo, kateri je večji.

Tukaj je 32 večje od 13 (32 > 13), tako da je že razvrščeno. Zdaj pa primerjajte 32 s 26.

Tu je 26 manjše od 36. Torej je potrebna zamenjava. Po zamenjavi bo nova matrika izgledala kot -

Zdaj pa primerjaj 32 in 35.

Tukaj je 35 večje od 32. Torej zamenjava ni potrebna, saj so že razvrščeni.

Zdaj bo primerjava med 35 in 10.

Tu je 10 manjše od 35, ki niso razvrščeni. Torej je potrebna menjava. Zdaj smo prišli do konca niza. Po prvem prehodu bo niz -

Zdaj pa pojdite na drugo ponovitev.

Drugi prehod

Enak postopek bo izveden za drugo ponovitev.

rihanna starost

Tukaj je 10 manjše od 32. Torej je potrebna zamenjava. Po zamenjavi bo niz -

Zdaj pa pojdite na tretjo ponovitev.

Tretji prehod

Enak postopek bo izveden za tretjo ponovitev.

Tukaj je 10 manjše od 26. Torej je potrebna zamenjava. Po zamenjavi bo niz -

Zdaj pa pojdite na četrto ponovitev.

Četrti prehod

Podobno bo po četrti ponovitvi niz -

Zato zamenjava ni potrebna, zato je matrika popolnoma razvrščena.

Kompleksnost razvrščanja mehurčkov

Zdaj pa poglejmo časovno kompleksnost razvrščanja z mehurčki v najboljšem, povprečnem in najslabšem primeru. Videli bomo tudi prostorsko kompleksnost razvrščanja mehurčkov.

1. Časovna zapletenost

Ovitek	Časovna zapletenost
Najboljši primer	O(n)
Povprečen primer	O(n²)
V najslabšem primeru	O(n²)

O(n).

O(n²).

2. Kompleksnost prostora

Kompleksnost prostora	O(1)
Stabilen	DA

Prostorska kompleksnost razvrščanja z mehurčki je O(1). To je zato, ker je pri mehurčastem razvrščanju za zamenjavo potrebna dodatna spremenljivka.
Prostorska kompleksnost optimiziranega mehurčkastega razvrščanja je O(2). To je zato, ker sta potrebni dve dodatni spremenljivki pri optimiziranem mehurčastem razvrščanju.

Zdaj pa se pogovorimo o optimiziranem algoritmu razvrščanja z mehurčki.

Optimiziran algoritem za razvrščanje z mehurčki

V algoritmu mehurčkovega razvrščanja se primerjave izvajajo tudi, ko je matrika že razvrščena. Zaradi tega se čas izvedbe poveča.

Za rešitev lahko uporabimo dodatno spremenljivko zamenjal. Nastavljen je na prav če je potrebna zamenjava; drugače je nastavljeno na lažno.

Koristno bo, kot recimo po ponovitvi, če ni potrebna zamenjava, vrednost spremenljivke zamenjal bo lažno. To pomeni, da so elementi že razvrščeni in nadaljnje ponovitve niso potrebne.

Ta metoda bo skrajšala čas izvajanja in tudi optimizirala razvrščanje oblačkov.

Algoritem za optimizirano razvrščanje mehurčkov

 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

Izvedba Bubble sort

Zdaj pa si oglejmo programe Bubble sort v različnih programskih jezikih.

ipconfig za ubuntu

Program: Napišite program za implementacijo mehurčkovega razvrščanja v jeziku 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;>

Izhod

Program: Napišite program za implementacijo mehurčkovega razvrščanja 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;>