bubble sort c with examples
Técnica de classificação por bolha em C ++.
O Bubble Sort é a mais simples das técnicas de classificação.
Na técnica de classificação por bolha, cada um dos elementos da lista é comparado ao seu elemento adjacente. Assim, se houver n elementos na lista A, então A [0] é comparado a A [1], A [1] é comparado a A [2] e assim por diante.
Depois de comparar se o primeiro elemento é maior que o segundo, os dois elementos são trocados.
=> Visite aqui para obter o curso C ++ completo com especialistas.
O que você aprenderá:
- Técnica de classificação de bolhas
- Ilustração
- Exemplo C ++
- Exemplo de Java
- Análise de complexidade do algoritmo de classificação de bolhas
- Conclusão
- Leitura recomendada
Técnica de classificação de bolhas
Usando a técnica de classificação por bolha, a classificação é feita em passagens ou iteração. Assim, no final de cada iteração, o elemento mais pesado é colocado em seu lugar apropriado na lista. Em outras palavras, o maior elemento da lista emerge.
Apresentamos abaixo um algoritmo geral da técnica de classificação de bolhas.
qual é a melhor remoção de malware
Algoritmo Geral
Passo 1 : Para i = 0 a N-1, repita a Etapa 2
Passo 2 : Para J = i + 1 a N - repito
etapa 3 : se A [J]> A [i]
Troque A [J] e A [i]
[Fim do Inner para loop]
[End if Outer for loop]
Passo 4 : Saída
Aqui está um pseudocódigo para o algoritmo de classificação por bolha, em que percorremos a lista usando dois loops iterativos.
No primeiro loop, começamos do 0ºelemento e no próximo loop, começamos a partir de um elemento adjacente. No corpo do loop interno, comparamos cada um dos elementos adjacentes e os trocamos se não estiverem em ordem. No final de cada iteração do loop externo, o elemento mais pesado borbulha no final.
Pseudo-código
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array[i-1] > array[i] then swap array[i-1] and array[i] swapped = true end if end for until not swapped end procedureO dado acima é o pseudo-código para a técnica de classificação por bolha. Vamos agora ilustrar essa técnica usando uma ilustração detalhada.
Ilustração
Pegamos uma matriz de tamanho 5 e ilustramos o algoritmo de classificação de bolhas.
Array totalmente classificado.
A ilustração acima pode ser resumida em uma forma tabular, conforme mostrado abaixo:
| Passar | Lista não classificada | comparação | Lista ordenada |
|---|---|---|---|
| {5,0,10,12,15} | {10,12} | {5,0,10,12,15} | |
| 1 | {10,5,15,0,12} | {10.5} | {5,10,15,0,12} |
| {5,10,15,0,12} | {10,15} | {5,10,15,0,12} | |
| {5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
| {5,10,0,15,12} | {15,12} | {5,10,0,12,15} | |
| dois | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
| {5,10,0,12,15} | {10,0} | {5,0,10,12,15} | |
| 3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
| {5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
| {5,0,10,12,15} | SORTED |
Conforme mostrado na ilustração, a cada passagem, o maior elemento borbulha até o último, classificando assim a lista a cada passagem. Conforme mencionado na introdução, cada elemento é comparado ao seu elemento adjacente e trocado um com o outro se eles não estiverem em ordem.
Assim, conforme mostrado na ilustração acima, no final da primeira passagem, se a matriz for classificada em ordem crescente, o maior elemento é colocado no final da lista. Para a segunda passagem, o segundo maior elemento é colocado na penúltima posição na lista e assim por diante.
Quando chegarmos a N-1 (onde N é um número total de elementos na lista), teremos toda a lista classificada.
A técnica de classificação por bolha pode ser implementada em qualquer linguagem de programação. Implementamos o algoritmo de classificação de bolhas usando a linguagem C ++ e Java abaixo.
como eu abro um arquivo bin
Exemplo C ++
Vejamos um exemplo de programação para demonstrar a classificação por bolha.
#include using namespace std; int main () { int i, j,temp,pass=0; int a[10] = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Resultado:
Lista de entrada ...
10 2 0 14 43 25 18 1 5 45
Lista de elementos classificados ...
0 1 2 5 10 14 18 25 43 45
Número de passes executados para classificar a lista: 10
Exemplo de Java
class Main { public static void main(String[] args) { int pass = 0; int[] a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a[i] + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a[i] Resultado:
c ++ gráfico não direcionado da lista de adjacência
Em ambos os programas, usamos uma matriz de 10 elementos e classificamos usando a técnica de classificação por bolha. Em ambos os programas, usamos dois loops for para iterar através dos elementos adjacentes do array.
No final de cada passagem (loop externo), o maior elemento na matriz é borbulhado até o final da matriz. Também contamos o número de passagens necessárias para classificar a matriz inteira.
Análise de complexidade do algoritmo de classificação de bolhas
A partir do pseudocódigo e da ilustração que vimos acima, na classificação por bolha, fazemos N-1 comparações na primeira passagem, N-2 comparações na segunda passagem e assim por diante.
Portanto, o número total de comparações na classificação por bolha é:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (ndois) => Complexidade de tempo da técnica de classificação de bolhas
Assim, as várias complexidades para a técnica de classificação de bolha são fornecidas abaixo:
Pior caso de complexidade de tempo O (n 2) Melhor caso de complexidade de tempo Sobre) Complexidade de tempo médio O (n 2) Complexidade do espaço O (1)
A técnica de classificação por bolha requer apenas um único espaço de memória adicional para a variável temp para facilitar a troca. Portanto, a complexidade do espaço para o algoritmo de classificação de bolhas é O (1).
Observe que o melhor caso de complexidade de tempo para a técnica de classificação por bolha será quando a lista já estiver classificada e será O (n).
Conclusão
A principal vantagem do Bubble Sort é a simplicidade do algoritmo. Na classificação por bolha, a cada passagem, o maior elemento borbulha até o final da lista se a matriz for classificada em ordem crescente.
Da mesma forma, para que a lista seja classificada em ordem decrescente, o menor elemento estará em seu lugar apropriado no final de cada passagem.
Sendo a técnica de classificação mais simples e fácil de implementar, a classificação por bolha geralmente é usada para apresentar a classificação ao público. Em segundo lugar, a classificação por bolhas também é usada em aplicativos como gráficos de computador, em que o preenchimento das bordas do polígono, etc. requer classificação por bolhas para classificar os vértices que revestem o polígono.
Em nosso próximo tutorial, aprenderemos sobre Classificação por seleção em detalhes.
=> Visite aqui para aprender C ++ do zero.
Leitura recomendada
- Classificação Shell em C ++ com exemplos
- Classificação de seleção em C ++ com exemplos
- Método MongoDB Sort () com exemplos
- Comando de classificação Unix com sintaxe, opções e exemplos
- Inserção de classificação em C ++ com exemplos
- Mesclar classificação em C ++ com exemplos
- Classificação de heap em C ++ com exemplos
- Classificação rápida em C ++ com exemplos
