Neste artigo, discutiremos o algoritmo de classificação por bolha. O procedimento de trabalho do tipo bolha é mais simples. Este artigo será muito útil e interessante para os alunos, pois eles podem enfrentar a classificação por bolhas como uma questão em seus exames. Então, é importante discutir o tema.
comando sed
A classificação por bolha funciona na troca repetida de elementos adjacentes até que eles não estejam na ordem pretendida. É chamado de classificação por bolha porque o movimento dos elementos da matriz é igual ao movimento das bolhas de ar na água. Bolhas na água sobem à superfície; da mesma forma, os elementos da matriz na classificação por bolha movem-se para o final em cada iteração.
Embora seja simples de usar, é usado principalmente como uma ferramenta educacional porque o desempenho do bubble sort é fraco no mundo real. Não é adequado para grandes conjuntos de dados. A complexidade média e de pior caso da classificação Bubble é Sobre2), onde n é uma série de itens.
Bubble short é usado principalmente onde -
- complexidade não importa
- simples e shortcode é o preferido
Algoritmo
No algoritmo fornecido abaixo, suponha chegar é uma matriz de n elementos. O suposto trocar A função no algoritmo trocará os valores de determinados elementos da matriz.
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
Funcionamento do algoritmo de classificação por bolha
Agora, vamos ver o funcionamento do algoritmo Bubble Sort.
Para entender o funcionamento do algoritmo de classificação por bolha, vamos pegar um array não classificado. Estamos pegando uma matriz curta e precisa, pois sabemos que a complexidade da classificação por bolha é Sobre2).
Deixe os elementos do array serem -
Primeira passagem
A classificação começará a partir dos dois elementos iniciais. Vamos compará-los para verificar qual é o maior.
Aqui, 32 é maior que 13 (32 > 13), então já está classificado. Agora, compare 32 com 26.
Aqui, 26 é menor que 36. Portanto, é necessária a troca. Após a troca, o novo array ficará assim -
Agora, compare 32 e 35.
Aqui, 35 é maior que 32. Portanto, não há necessidade de troca, pois eles já estão classificados.
Agora, a comparação ficará entre 35 e 10.
sistemas operacionais mac
Aqui, 10 é menor que 35 que não estão classificados. Portanto, a troca é necessária. Agora, chegamos ao final do array. Após a primeira passagem, o array será -
Agora, vá para a segunda iteração.
Segunda passagem
O mesmo processo será seguido para a segunda iteração.
Aqui, 10 é menor que 32. Portanto, é necessária a troca. Após a troca, o array será -
Agora, vá para a terceira iteração.
Terceira passagem
O mesmo processo será seguido para a terceira iteração.
Aqui, 10 é menor que 26. Portanto, é necessária a troca. Após a troca, o array será -
Agora, vá para a quarta iteração.
Quarta passagem
Da mesma forma, após a quarta iteração, o array será -
Portanto, não há necessidade de troca, portanto o array está completamente classificado.
Complexidade de classificação por bolha
Agora, vamos ver a complexidade de tempo da classificação por bolha no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial da classificação por bolha.
1. Complexidade de tempo
| Caso | Complexidade de tempo |
|---|---|
| Melhor caso | Sobre) |
| Caso médio | Sobre2) |
| Pior caso | Sobre2) |
2. Complexidade Espacial
| Complexidade Espacial | O(1) |
| Estábulo | SIM |
- A complexidade espacial da classificação por bolha é O (1). Isso ocorre porque, na classificação por bolha, uma variável extra é necessária para a troca.
- A complexidade espacial da classificação por bolha otimizada é O(2). Isso ocorre porque duas variáveis extras são necessárias na classificação por bolha otimizada.
Agora, vamos discutir o algoritmo otimizado de classificação por bolha.
Algoritmo de classificação de bolha otimizado
No algoritmo de classificação por bolha, as comparações são feitas mesmo quando o array já está classificado. Por causa disso, o tempo de execução aumenta.
Para resolvê-lo, podemos usar uma variável extra trocado. Está definido para verdadeiro se a troca exigir; caso contrário, está definido para falso.
Será útil, como suponhamos que após uma iteração, se não houver necessidade de troca, o valor da variável trocado vai ser falso. Isso significa que os elementos já estão classificados e nenhuma iteração adicional é necessária.
Este método reduzirá o tempo de execução e também otimizará a classificação por bolha.
Algoritmo para classificação de bolhas otimizada
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
Implementação de classificação por bolha
Agora, vamos ver os programas de classificação Bubble em diferentes linguagens de programação.
comandos kali linux
Programa: Escreva um programa para implementar a classificação por bolha em linguagem 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>'); 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;> Saída
Programa: Escreva um programa para implementar a classificação por bolha em 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>'; 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;> Saída
Programa: Escreva um programa para implementar a classificação por bolha em python.
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]:>