ORDINAMENTO A BOLLE - TUTORIAL DS

In questo articolo discuteremo dell'algoritmo Bubble sort. La procedura operativa del Bubble Sort è la più semplice. Questo articolo sarà molto utile e interessante per gli studenti poiché potrebbero dover affrontare il bubble sort come domanda durante i loro esami. Quindi è importante discutere l’argomento.

scorciatoie di Linux

L'ordinamento a bolle funziona sullo scambio ripetuto di elementi adiacenti fino a quando non si trovano nell'ordine previsto. Si chiama bubble sort perché il movimento degli elementi dell'array è proprio come il movimento delle bolle d'aria nell'acqua. Le bolle nell'acqua salgono in superficie; allo stesso modo, gli elementi dell'array nel bubble sort si spostano alla fine in ogni iterazione.

Sebbene sia semplice da usare, viene utilizzato principalmente come strumento educativo perché le prestazioni del Bubble Sort sono scarse nel mondo reale. Non è adatto per set di dati di grandi dimensioni. La complessità media e nel caso peggiore del Bubble sort è SU²), Dove N è un numero di elementi.

Bubble short viene utilizzato principalmente dove:

la complessità non ha importanza
è preferibile il semplice e lo shortcode

Algoritmo

Nell'algoritmo fornito di seguito, supponiamo arr è un array di N elementi. Il presunto scambio La funzione nell'algoritmo scambierà i valori di determinati elementi dell'array.

 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

Funzionamento dell'algoritmo Bubble Sort

Ora vediamo il funzionamento dell'algoritmo Bubble Sort.

Per comprendere il funzionamento dell'algoritmo di bubble sort, prendiamo un array non ordinato. Stiamo prendendo una matrice breve e accurata, poiché sappiamo quanto sia complessa l'ordinamento delle bolle SU²).

Lascia che gli elementi dell'array siano -

Primo passaggio

L'ordinamento inizierà dai due elementi iniziali. Confrontiamoli per verificare quale è maggiore.

Qui 32 è maggiore di 13 (32 > 13), quindi è già ordinato. Ora confrontiamo 32 con 26.

Qui, 26 è inferiore a 36. Quindi è necessario lo scambio. Dopo aver scambiato il nuovo array apparirà come:

Ora confrontiamo 32 e 35.

Qui, 35 è maggiore di 32. Quindi, non è necessario scambiarli poiché sono già ordinati.

Ora il confronto sarà tra 35 e 10.

Qui, 10 è inferiore a 35 che non sono ordinati. Quindi è necessario lo scambio. Ora raggiungiamo la fine dell'array. Dopo il primo passaggio, l'array sarà:

Ora passiamo alla seconda iterazione.

Secondo passaggio

Lo stesso procedimento verrà seguito per la seconda iterazione.

Qui, 10 è inferiore a 32. Quindi è necessario lo scambio. Dopo lo scambio, l'array sarà:

Ora passiamo alla terza iterazione.

Terzo passaggio

Lo stesso procedimento verrà seguito per la terza iterazione.

Qui, 10 è inferiore a 26. Quindi è necessario lo scambio. Dopo lo scambio, l'array sarà:

Ora passiamo alla quarta iterazione.

Quarto passaggio

Allo stesso modo, dopo la quarta iterazione, l'array sarà -

altera aggiungi colonna Oracle

Pertanto, non è richiesto alcuno scambio, quindi l'array è completamente ordinato.

Complessità dell'ordinamento delle bolle

Ora, vediamo la complessità temporale del bubble sort nel caso migliore, medio e peggiore. Vedremo anche la complessità spaziale del bubble sort.

1. Complessità temporale

Caso	Complessità temporale
Caso migliore	SU)
Caso medio	SU²)
Caso peggiore	SU²)

SU).

SU²).

2. Complessità spaziale

Complessità spaziale	O(1)
Stabile	SÌ

La complessità spaziale del bubble sort è O(1). Questo perché, nel bubble sort, è necessaria una variabile aggiuntiva per lo scambio.
La complessità spaziale del bubble sort ottimizzato è O(2). Ciò avviene perché sono necessarie due variabili aggiuntive nell'ordinamento a bolle ottimizzato.

Ora parliamo dell'algoritmo ottimizzato di bubble sort.

Algoritmo di ordinamento delle bolle ottimizzato

Nell'algoritmo di ordinamento a bolle, i confronti vengono effettuati anche quando l'array è già ordinato. Per questo motivo, il tempo di esecuzione aumenta.

Per risolverlo, possiamo usare una variabile extra scambiato. È impostato su VERO se lo scambio richiede; in caso contrario, è impostato su falso.

Sarà utile, come supponiamo dopo un'iterazione, se non è richiesto lo scambio, il valore della variabile scambiato sarà falso. Significa che gli elementi sono già ordinati e non sono necessarie ulteriori iterazioni.

Questo metodo ridurrà il tempo di esecuzione e ottimizzerà anche il bubble sort.

Algoritmo per il bubble sort ottimizzato

 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

Implementazione del Bubble Sort

Vediamo ora i programmi di Bubble Sort nei diversi linguaggi di programmazione.

1 milione di numeri

Programma: Scrivere un programma per implementare il bubble sort in linguaggio 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;>

Produzione

Programma: Scrivi un programma per implementare il bubble sort in 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;>

Produzione

Programma: Scrivi un programma per implementare il bubble sort in Python.

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