SORTARE CU BULE - TUTORIAL DS

În acest articol, vom discuta despre algoritmul de sortare cu bule. Procedura de lucru de sortare cu bule este cea mai simplă. Acest articol va fi foarte util și interesant pentru studenți, deoarece s-ar putea confrunta cu sortarea cu bule ca întrebare în examenele lor. Deci, este important să discutăm subiectul.

metode matematice în java

Sortarea cu bule funcționează la schimbarea în mod repetat a elementelor adiacente până când acestea nu sunt în ordinea dorită. Se numește sortare cu bule, deoarece mișcarea elementelor matricei este la fel ca mișcarea bulelor de aer în apă. Bulele din apă se ridică la suprafață; în mod similar, elementele matricei din sortarea cu bule se deplasează la sfârșitul fiecărei iterații.

Deși este simplu de utilizat, este folosit în primul rând ca instrument educațional, deoarece performanța sortării cu bule este slabă în lumea reală. Nu este potrivit pentru seturi mari de date. Complexitatea medie și cel mai rău caz a sortării cu bule este Pe²), Unde n este un număr de articole.

Bubble short este utilizat în principal acolo unde -

complexitatea nu contează
simplu și shortcode este de preferat

Algoritm

În algoritmul de mai jos, să presupunem arr este o serie de n elemente. Asumat schimb funcția din algoritm va schimba valorile elementelor de matrice date.

 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

Funcționarea algoritmului de sortare cu bule

Acum, să vedem funcționarea algoritmului de sortare cu bule.

Pentru a înțelege funcționarea algoritmului de sortare cu bule, să luăm o matrice nesortată. Luăm o matrice scurtă și precisă, așa cum știm că este complexitatea sortării cu bule Pe²).

Fie elementele matricei sunt -

Prima trecere

Sortarea va începe de la primele două elemente. Să le comparăm pentru a verifica care este mai mare.

Aici, 32 este mai mare decât 13 (32 > 13), deci este deja sortat. Acum, compară 32 cu 26.

Aici, 26 este mai mic decât 36. Deci, este necesară schimbarea. După schimbarea matricei noi va arăta ca -

Acum, compară 32 și 35.

Aici, 35 este mai mare decât 32. Deci, nu este necesară schimbarea, deoarece acestea sunt deja sortate.

Acum, comparația va fi între 35 și 10.

Aici, 10 este mai mic decât 35 care nu sunt sortate. Deci, este necesară schimbarea. Acum ajungem la sfârșitul matricei. După prima trecere, matricea va fi -

Acum, treceți la a doua iterație.

A doua trecere

Același proces va fi urmat pentru a doua iterație.

Aici, 10 este mai mic decât 32. Deci, este necesară schimbarea. După schimbare, matricea va fi -

Acum, treceți la a treia iterație.

A treia trecere

Același proces va fi urmat pentru a treia iterație.

algoritm de programare round robin

Aici, 10 este mai mic decât 26. Deci, este necesară schimbarea. După schimbare, matricea va fi -

Acum, treceți la a patra iterație.

A patra trecere

În mod similar, după a patra iterație, matricea va fi -

Prin urmare, nu este necesară schimbarea, astfel încât matricea este complet sortată.

Complexitatea sortării cu bule

Acum, să vedem complexitatea de timp a sortării cu bule în cel mai bun caz, caz mediu și cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a sortării cu bule.

1. Complexitatea timpului

Caz	Complexitatea timpului
Cel mai bun caz	Pe)
Caz mediu	Pe²)
Cel mai rău caz	Pe²)

Pe).

Pe²).

2. Complexitatea spațială

Complexitatea spațială	O(1)
Grajd	DA

Complexitatea spațială a sortării cu bule este O(1). Se datorează faptului că, în sortarea cu bule, este necesară o variabilă suplimentară pentru schimbare.
Complexitatea spațială a sortării cu bule optimizate este O(2). Se datorează faptului că sunt necesare două variabile suplimentare în sortarea optimizată cu bule.

Acum, să discutăm despre algoritmul optimizat de sortare cu bule.

Algoritm de sortare cu bule optimizat

În algoritmul de sortare cu bule, comparațiile sunt făcute chiar și atunci când matricea este deja sortată. Din această cauză, timpul de execuție crește.

Pentru a o rezolva, putem folosi o variabilă suplimentară schimbat. Este setat la Adevărat dacă schimbarea necesită; în caz contrar, este setat la fals.

Va fi util, după cum presupunem după o iterație, dacă nu este necesară schimbarea, valoarea variabilei schimbat va fi fals. Înseamnă că elementele sunt deja sortate și nu sunt necesare alte iterații.

Această metodă va reduce timpul de execuție și, de asemenea, va optimiza sortarea cu bule.

Algoritm pentru sortarea optimizată a bulelor

 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

Implementarea sortării cu bule

Acum, să vedem programele de sortare Bubble în diferite limbaje de programare.

convertiți șirul în int în java

Program: Scrieți un program pentru a implementa sortarea cu bule în limbajul 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;>

Ieșire

Program: Scrieți un program pentru a implementa sortarea cu bule în 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;>