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ä2), 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ä2).
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
| Asia | Aika monimutkaisuus |
|---|---|
| Paras tapaus | Päällä) |
| Keskimääräinen tapaus | Päällä2) |
| Pahimmassa tapauksessa | Päällä2) |
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O(1) |
| Vakaa | JOO |
- 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>'); 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 - ' + ' <br>'); 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>'; 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>'; printArray($a); ?> </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('Before sorting array elements are - ') for i in a: print(i, end = ' ') 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'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'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>'; 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>'; printArray($a); ?> </5;> Lähtö
Ohjelmoida: Kirjoita ohjelma kuplalajittelun toteuttamiseksi pythonissa.
a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') 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'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's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>