BURBULŲ RŪŠIAVIMAS

Šiame straipsnyje aptarsime burbulų rūšiavimo algoritmą. Burbulinio rūšiavimo darbo procedūra yra pati paprasčiausia. Šis straipsnis bus labai naudingas ir įdomus studentams, nes egzaminuose jie gali susidurti su burbulų rūšiavimo klausimu. Taigi, svarbu aptarti temą.

baitų į eilutę python

Burbulinis rūšiavimas veikia pakartotinai keičiant gretimus elementus, kol jie nėra numatytos tvarkos. Jis vadinamas burbulų rūšiavimu, nes masyvo elementų judėjimas yra toks pat kaip oro burbuliukų judėjimas vandenyje. Vandenyje esantys burbuliukai pakyla į paviršių; panašiai, burbulų rūšiavimo masyvo elementai kiekvienos iteracijos metu pereina į pabaigą.

Nors jį paprasta naudoti, jis pirmiausia naudojamas kaip mokomoji priemonė, nes realiame pasaulyje burbulų rūšiavimo našumas yra prastas. Jis netinka dideliems duomenų rinkiniams. Vidutinis ir blogiausias „Bubble“ rūšiavimo sudėtingumas yra O (n²), kur n yra keletas elementų.

„Bubble Short“ dažniausiai naudojamas ten, kur -

sudėtingumas nesvarbu
pageidautina paprastas ir trumpasis kodas

Algoritmas

Tarkime, kad toliau pateiktame algoritme arr yra masyvas n elementai. Tariamas apsikeisti funkcija algoritme sukeis nurodytų masyvo elementų reikšmes.

 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

Burbulų rūšiavimo algoritmo veikimas

Dabar pažiūrėkime, kaip veikia burbulų rūšiavimo algoritmas.

Norėdami suprasti, kaip veikia burbulų rūšiavimo algoritmas, paimkime nerūšiuotą masyvą. Mes naudojame trumpą ir tikslų masyvą, nes žinome, koks yra burbulų rūšiavimo sudėtingumas O (n²).

Tegul masyvo elementai yra -

Pirmasis leidimas

Rūšiavimas prasidės nuo dviejų pradinių elementų. Palyginkite juos ir patikrinkite, kuris yra didesnis.

Čia 32 yra didesnis nei 13 (32 > 13), taigi jis jau surūšiuotas. Dabar palyginkite 32 su 26.

Čia 26 yra mažesnis nei 36. Taigi, reikia pakeisti. Pakeitus naujas masyvas atrodys taip -

Dabar palyginkite 32 ir 35.

Čia 35 yra didesnis nei 32. Taigi, keisti nereikia, nes jie jau surūšiuoti.

Dabar palyginimas bus nuo 35 iki 10.

Čia 10 yra mažesni nei 35, kurie nėra surūšiuoti. Taigi, reikia keisti. Dabar pasiekiame masyvo pabaigą. Po pirmojo praėjimo masyvas bus -

Dabar pereikite prie antrosios iteracijos.

Antrasis leidimas

Tas pats procesas bus atliktas ir antrą kartą.

Čia 10 yra mažesnis nei 32. Taigi, reikia keisti. Po pakeitimo masyvas bus -

Dabar pereikite prie trečiosios iteracijos.

Trečias leidimas

Tas pats procesas bus vykdomas trečią kartą.

Čia 10 yra mažesnis nei 26. Taigi, reikia pakeisti. Po pakeitimo masyvas bus -

Dabar pereikite prie ketvirtosios iteracijos.

Ketvirtas praėjimas

Panašiai po ketvirtosios iteracijos masyvas bus -

Sąrašo kūrimas java

Taigi, keisti nereikia, todėl masyvas yra visiškai surūšiuotas.

Burbulų rūšiavimo sudėtingumas

Dabar pažiūrėkime, koks yra burbulų rūšiavimo sudėtingumas geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime burbulų rūšiavimo erdvės sudėtingumą.

1. Laiko sudėtingumas

Byla	Laiko sudėtingumas
Geriausias atvejis	O(n)
Vidutinis atvejis	O (n²)
Blogiausiu atveju	O (n²)

O(n).

O (n²).

2. Erdvės sudėtingumas

Erdvės sudėtingumas	O(1)
Stabilus	TAIP

Burbulų rūšiavimo erdvės sudėtingumas yra O(1). Taip yra todėl, kad rūšiuojant burbulą, norint pakeisti, reikalingas papildomas kintamasis.
Optimizuoto burbulų rūšiavimo erdvės sudėtingumas yra O(2). Taip yra todėl, kad optimizuotam burbulų rūšiavimui reikalingi du papildomi kintamieji.

Dabar aptarkime optimizuotą burbulų rūšiavimo algoritmą.

Optimizuotas burbulų rūšiavimo algoritmas

Burbulų rūšiavimo algoritme lyginami net tada, kai masyvas jau surūšiuotas. Dėl to pailgėja vykdymo laikas.

Norėdami tai išspręsti, galime naudoti papildomą kintamąjį apsikeitė. Jis nustatytas į tiesa jei reikia pakeisti; kitu atveju jis nustatytas klaidinga.

Tai bus naudinga, kaip tarkime, po iteracijos, jei nereikia keisti, kintamojo reikšmė apsikeitė bus klaidinga. Tai reiškia, kad elementai jau yra surūšiuoti ir nereikia atlikti papildomų iteracijų.

Šis metodas sumažins vykdymo laiką ir optimizuos burbulų rūšiavimą.

Optimizuoto burbulų rūšiavimo algoritmas

 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

Burbulų rūšiavimo įgyvendinimas

Dabar pažiūrėkime, kaip „Bubble“ rūšiuojamos skirtingomis programavimo kalbomis.

avl medžio sukimasis

Programa: Parašykite programą, kuri įgyvendintų burbulų rūšiavimą C kalba.

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

Išvestis

Programa: Parašykite programą burbulų rūšiavimui PHP įdiegti.

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