Tässä artikkelissa keskustelemme kuplalajittelualgoritmista. Kuplalajittelun toimintatapa on yksinkertaisin. Tämä artikkeli on erittäin hyödyllinen ja mielenkiintoinen opiskelijoille, koska he saattavat kohdata kuplalajittelun kysymyksenä kokeissaan. Joten on tärkeää keskustella aiheesta.

muuntaa merkkijono json-objektiksi

Kuplalajittelu toimii vierekkäisten elementtien toistuvalla vaihdolla, kunnes ne eivät ole aiotussa järjestyksessä. Sitä kutsutaan kuplalajitukseksi, koska ryhmän elementtien liike on aivan kuten ilmakuplien liike vedessä. Vedessä olevat kuplat nousevat pintaan; samoin kuplalajittelun taulukkoelementit siirtyvät jokaisen iteroinnin loppuun.

Vaikka se on helppokäyttöinen, sitä käytetään ensisijaisesti opetusvälineenä, koska kuplalajittelun suorituskyky on huono todellisessa maailmassa. Se ei sovellu suurille tietojoukoille. Bubble-lajittelun keskimääräinen ja pahimman tapauksen monimutkaisuus on Päällä²), missä n on useita kohteita.

Bubble shortta käytetään pääasiassa missä -

• monimutkaisuudella ei ole väliä
• yksinkertainen ja lyhytkoodi on parempi

Algoritmi

Oletetaan alla olevassa algoritmissa arr on joukko n elementtejä. Oletettu vaihtaa algoritmin funktio vaihtaa tiettyjen taulukon elementtien arvot.

 begin BubbleSort(arr) for all array elements if arr[i] > arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort 

Bubble sort -algoritmin toiminta

Katsotaan nyt, miten Bubble sort algoritmi toimii.

Ymmärtääksemme kuplalajittelualgoritmin toiminnan, otetaan lajittelematon matriisi. Otamme lyhyen ja tarkan taulukon, koska tiedämme kuplalajittelun monimutkaisuuden Päällä²).

Olkoon taulukon elementit -

Ensimmäinen passi

Lajittelu alkaa kahdesta ensimmäisestä elementistä. Vertaa niitä tarkistaaksesi kumpi on suurempi.

Tässä 32 on suurempi kuin 13 (32 > 13), joten se on jo lajiteltu. Vertaa nyt 32:ta 26:een.

Tässä 26 on pienempi kuin 36. Joten vaihto on tarpeen. Vaihdon jälkeen uusi taulukko näyttää tältä -

Vertaa nyt 32 ja 35.

Tässä 35 on suurempi kuin 32. Joten vaihtamista ei tarvita, koska ne on jo lajiteltu.

Nyt vertailu on 35 ja 10 välillä.

Tässä 10 on pienempi kuin 35, joita ei ole lajiteltu. Eli vaihto on tarpeen. Nyt päästään taulukon loppuun. Ensimmäisen läpikäynnin jälkeen matriisi on -

Siirry nyt toiseen iteraatioon.

Toinen passi

Samaa prosessia noudatetaan toisessa iteraatiossa.

Tässä 10 on pienempi kuin 32. Joten vaihto on tarpeen. Vaihdon jälkeen matriisi on -

Siirry nyt kolmanteen iteraatioon.

Kolmas passi

Samaa prosessia noudatetaan kolmannessa iteraatiossa.

Tässä 10 on pienempi kuin 26. Joten vaihto on tarpeen. Vaihdon jälkeen matriisi on -

Siirry nyt neljänteen iteraatioon.

Neljäs passi

Vastaavasti neljännen iteraation jälkeen matriisi on -

css läpinäkyvyyden siirtyminen

Siten vaihtamista ei tarvita, joten matriisi on täysin lajiteltu.

Kuplalajittelun monimutkaisuus

Katsotaan nyt kuplalajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös kuplalajittelun avaruuden monimutkaisuuden.

1. Aika monimutkaisuus

Paras tapauksen monimutkaisuus -Se tapahtuu, kun lajittelua ei vaadita, eli matriisi on jo lajiteltu. Kuplalajittelun paras aika monimutkaisuus on Päällä). Keskimääräinen tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit ovat sekaisin järjestyksessä, joka ei ole oikein nouseva eikä oikein laskeva. Keskimääräinen kuplalajittelun tapauksen aika monimutkaisuus on Päällä²). Pahimman tapauksen monimutkaisuus -Se tapahtuu, kun taulukon elementit on lajiteltava käänteisessä järjestyksessä. Tämä tarkoittaa, että sinun on lajiteltava taulukon elementit nousevaan järjestykseen, mutta sen elementit ovat laskevassa järjestyksessä. Kuplalajittelun pahin aikamonimutkaisuus on Päällä²).

2. Tilan monimutkaisuus

• Kuplalajittelun avaruuden monimutkaisuus on O(1). Tämä johtuu siitä, että kuplalajittelussa vaihtoon tarvitaan ylimääräinen muuttuja.
• Optimoidun kuplalajittelun tilamonimutkaisuus on O(2). Tämä johtuu siitä, että optimoituun kuplalajitteluun tarvitaan kaksi ylimääräistä muuttujaa.

Nyt keskustellaan optimoidusta kuplalajittelualgoritmista.

Optimoitu kuplalajittelualgoritmi

Kuplalajittelualgoritmissa vertailuja tehdään silloinkin, kun taulukko on jo lajiteltu. Tästä johtuen suoritusaika pitenee.

Sen ratkaisemiseksi voimme käyttää ylimääräistä muuttujaa vaihdettu. Se on asetettu totta jos vaihto vaatii; muuten se on asetettu väärä.

Oletetaan iteraation jälkeen, jos vaihtoa ei tarvita, muuttujan arvo vaihdettu tulee olemaan väärä. Se tarkoittaa, että elementit on jo lajiteltu, eikä muita iteraatioita tarvita.

Tämä menetelmä vähentää suoritusaikaa ja optimoi myös kuplalajittelun.

Optimoidun kuplalajittelun algoritmi

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] > array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort 

Bubble sortin käyttöönotto

Katsotaanpa nyt Bubble-lajiteltuja ohjelmia eri ohjelmointikielillä.

ssh täysi muoto

Ohjelmoida: Kirjoita ohjelma kuplalajittelun toteuttamiseksi C-kielellä.

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

Lähtö

Ohjelmoida: Kirjoita ohjelma kuplalajittelun toteuttamiseksi PHP:ssä.

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

Lähtö

Ohjelmoida: Kirjoita ohjelma kuplalajittelun toteuttamiseksi pythonissa.

 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]:>