BURBUĻU KĀRTOŠANA - DS APMĀCĪBA

Šajā rakstā mēs apspriedīsim burbuļu kārtošanas algoritmu. Burbuļu šķirošanas darba procedūra ir visvienkāršākā. Šis raksts būs ļoti noderīgs un interesants studentiem, jo viņi eksāmenos var saskarties ar burbuļu kārtošanas jautājumu. Tāpēc ir svarīgi apspriest tēmu.

js komplekts

Burbuļu kārtošana darbojas, atkārtoti apmainot blakus esošos elementus, līdz tie nav paredzētajā secībā. To sauc par burbuļu šķirošanu, jo masīva elementu kustība ir tāpat kā gaisa burbuļu kustība ūdenī. Burbuļi ūdenī paceļas līdz virsmai; līdzīgi masīva elementi burbuļu kārtošanā katrā iterācijā pārvietojas uz beigām.

Lai gan tas ir vienkārši lietojams, tas galvenokārt tiek izmantots kā izglītojošs līdzeklis, jo reālajā pasaulē burbuļu šķirošanas veiktspēja ir slikta. Tas nav piemērots lielām datu kopām. Bubble sortēšanas vidējā un sliktākā gadījuma sarežģītība ir O(n²), kur n ir vairākas preces.

Bubble short galvenokārt tiek izmantots, kur -

sarežģītībai nav nozīmes
priekšroka tiek dota vienkāršam un īsajam kodam

Algoritms

Pieņemsim, ka tālāk sniegtajā algoritmā arr ir masīvs n elementi. Pieņemtais mijmaiņa funkcija algoritmā apmainīs doto masīva elementu vērtības.

 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

Burbuļu šķirošanas algoritma darbība

Tagad apskatīsim burbuļu kārtošanas algoritma darbību.

Lai saprastu burbuļu kārtošanas algoritma darbību, ņemsim nešķirotu masīvu. Mēs izmantojam īsu un precīzu masīvu, jo mēs zinām, ka burbuļu kārtošana ir sarežģīta O(n²).

Lai masīva elementi ir -

Pirmā caurlaide

Kārtošana sāksies no diviem sākotnējiem elementiem. Salīdziniet tos, lai pārbaudītu, kurš ir lielāks.

Šeit 32 ir lielāks par 13 (32 > 13), tāpēc tas jau ir sakārtots. Tagad salīdziniet 32 ar 26.

Šeit 26 ir mazāks par 36. Tātad ir nepieciešama maiņa. Pēc nomaiņas jaunais masīvs izskatīsies šādi -

Tagad salīdziniet 32. un 35.

Šeit 35 ir lielāks par 32. Tātad nav jāmaina, jo tie jau ir sakārtoti.

Tagad salīdzinājums būs no 35 līdz 10.

Šeit 10 ir mazāki par 35, kas nav sakārtoti. Tātad ir nepieciešama maiņa. Tagad mēs sasniedzam masīva galu. Pēc pirmās piespēles masīvs būs -

Tagad pārejiet uz otro atkārtojumu.

Otrā caurlaide

Tas pats process tiks veikts arī otrajai iterācijai.

Šeit 10 ir mazāks par 32. Tātad ir nepieciešama maiņa. Pēc apmaiņas masīvs būs -

Tagad pārejiet uz trešo atkārtojumu.

Trešā caurlaide

Tas pats process tiks veikts trešajā atkārtojumā.

Android tālruņa iestatījumu izvēlne

Šeit 10 ir mazāks par 26. Tātad ir nepieciešama maiņa. Pēc apmaiņas masīvs būs -

Tagad pārejiet uz ceturto atkārtojumu.

Ceturtā piespēle

Tāpat pēc ceturtās iterācijas masīvs būs -

Līdz ar to nav nepieciešama mijmaiņa, tāpēc masīvs ir pilnībā sakārtots.

Burbuļu šķirošanas sarežģītība

Tagad apskatīsim burbuļu kārtošanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī burbuļu šķirošanas telpas sarežģītību.

1. Laika sarežģītība

Lieta	Laika sarežģītība
Labākais gadījums	O(n)
Vidējais gadījums	O(n²)
Sliktākajā gadījumā	O(n²)

O(n).

O(n²).

2. Telpas sarežģītība

Kosmosa sarežģītība	O(1)
Stabils	JĀ

Burbuļu kārtošanas telpas sarežģītība ir O(1). Tas ir tāpēc, ka burbuļu kārtošanā apmaiņai ir nepieciešams papildu mainīgais.
Optimizētās burbuļu kārtošanas telpas sarežģītība ir O(2). Tas ir tāpēc, ka optimizētajā burbuļu kārtošanā ir nepieciešami divi papildu mainīgie.

Tagad apspriedīsim optimizēto burbuļu kārtošanas algoritmu.

Optimizēts burbuļu kārtošanas algoritms

Burbuļu kārtošanas algoritmā salīdzinājumi tiek veikti pat tad, ja masīvs jau ir sakārtots. Sakarā ar to izpildes laiks palielinās.

Lai to atrisinātu, mēs varam izmantot papildu mainīgo apmainīts. Tas ir iestatīts uz taisnība ja nepieciešama maiņa; pretējā gadījumā tas ir iestatīts uz viltus.

Tas būs noderīgi, piemēram, pēc iterācijas, ja nav nepieciešama mijmaiņa, mainīgā vērtība apmainīts būs viltus. Tas nozīmē, ka elementi jau ir sakārtoti, un turpmākas iterācijas nav nepieciešamas.

Šī metode samazinās izpildes laiku un arī optimizēs burbuļu kārtošanu.

Algoritms optimizētai burbuļu šķirošanai

 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

Bubble sort ieviešana

Tagad apskatīsim Bubble kārtošanas programmas dažādās programmēšanas valodās.

kārtot masīvu sarakstu

Programma: Uzrakstiet programmu burbuļu kārtošanai C valodā.

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

Izvade

Programma: Uzrakstiet programmu burbuļu kārtošanai 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;>