Programa C para classificação de bolhas: classificação de bolhas em C

Introdução

A classificação de uma matriz ocupa um lugar de imensa importância na ciência da computação. Sua utilidade é percebida quando há a necessidade de organizar os dados em uma ordem específica. Existem diferentes tipos de algoritmos de ordenação. O algoritmo de ordenação mais comum e amplamente utilizado é o Bubble Sort.

Ordenação de bolhas em C

A técnica que é usada para ordenar no Bubble sort é simples e fácil de entender. Tudo o que faz é comparar o elemento atual com o próximo elemento e trocá-lo se for maior ou menor, conforme ditado pela condição. O algoritmo é muito preciso. Cada vez que um elemento é comparado com outros elementos até que seu lugar seja encontrado, ele é chamado de passagem.

Esse algoritmo é comparável a bolhas na água, pois filtra o topo das bolhas semelhantes a matrizes. Entre todos os algoritmos usados ​​para ordenação, o Bubble sort é o mais fácil e o mais lento com complexidade de tempo O(n^2). No entanto, o algoritmo pode ser otimizado através do uso de uma variável sinalizadora que sai do loop quando a troca é concluída. O melhor caso para a ordenação por bolha pode ser O(n) quando a matriz é ordenada.

Por exemplo, vamos pegar uma matriz não classificada de cinco números, conforme indicado abaixo

13, 32,26, 34,9

A ordenação por bolha começará a considerar os dois primeiros elementos e os comparará para verificar qual deles é maior. Nesse caso, 32 é maior que 13. Portanto, essa parte já está classificada em y. Em seguida, comparamos 32 com 26. Então descobrimos que 32 é maior que 26, então eles devem ser trocados. A nova matriz será semelhante

13, 26, 32,34,9

Em seguida, comparamos 32 e 34. Sabemos que já estão ordenados. Assim, passamos para as duas últimas variáveis ​​34 e 9. Como 34 é maior que 9, elas precisam ser trocadas.

Trocamos os valores e chegamos ao final do array após a primeira iteração. Agora a matriz ficará assim

13, 26. 32,9,34

Após a segunda iteração, a matriz será semelhante

13, 26, 9,32,34

Após a terceira iteração, o array se tornará

13,9,26,32,34

Após a quarta iteração, a matriz será completamente classificada

9, 13,26,32,34

Deve ler: ideias de projetos em C

O algoritmo

Aqui estamos assumindo que a matriz tem n elementos. Além disso, assumimos que a função de troca de valores está trocando todos os valores para tornar os números da matriz em ordem de classificação.

iniciar BubbleSort (matriz)

para todos os elementos da lista

if array[i]> array[i+1]

valores de troca(array[i], array[i+1])

fim se

fim para

matriz de retorno

fim da classificação de bolhas

Leia: Classificação na estrutura de dados: categorias e tipos

Pseudo-código

É evidente no algoritmo acima que há uma comparação entre cada par do elemento do array até que todo o array seja ordenado em ordem crescente. Isso pode resultar em alguns problemas de complexidade, como o resultado do algoritmo quando a matriz já está classificada em ordem crescente. Para facilitar o problema, usaremos uma variável sinalizadora, que nos permite ver se houve alguma troca. Se não for necessária mais troca, sairemos do loop interno.

O pseudocódigo para o algoritmo BubbleSort pode ser escrito da seguinte forma

procedimento BubbleSort (array: itens no array)

iterar= array.count;

para k=0 para iterar-1 faça:

bandeira = falso

para l=0 para iterar-1 faça:

if (array[l]> array[l+1]) então

valores de troca(array[l], array [l+1])

flag=true

fim se

fim para

Se (não trocado) então

Pausa

Fim se

Fim para

Fim da matriz de retorno do procedimento

Vamos experimentar um programa de exemplo de ordenação por bolhas em C :

# inclui<stdio.h>

vazio principal

{

int array [10], i, j, num

para (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

if(matriz[j]>matriz[j+1])

{

num= array[j];

matriz[j]=matriz[j+1];

matriz[j+1]=num;

}

}

}

printf("A matriz ordenada é /n");

for(i=0;i<=9;i++)

{

printf("%d",&array[i])

}

}

Conforme mostrado no exemplo, esse algoritmo de classificação de bolhas aceita 10 números do usuário e os armazena na matriz. Na próxima parte, há dois loops for. O loop externo é executado para o valor I, igualando zero a menor que igual a nove. A função do loop externo é cuidar de todos os elementos do valor que devem ser comparados com outros elementos.

Há outro loop dentro do loop externo. Ele começa em j=0 e vai até ser menor ou igual a oito. Dentro, há uma instrução condicional if que compara e verifica se array[j] é maior que array [j+1]. Se a condição for satisfeita, os valores de array[j] e array [j+1] são trocados entre si.

Uma variável com o nome de num é usada para esta finalidade. Primeiro array[j] é atribuído a num, depois array[j+1] é atribuído a array[j], e finalmente num é atribuído a array[j+1]. Esse processo continuará até que todos os elementos da matriz sejam classificados em ordem crescente. Depois disso, o array ordenado é impresso.

Implementação otimizada do Bubble Sort

Temos um algoritmo otimizado para classificação de bolhas para melhorar os resultados. O uso de uma variável flag faz a otimização. A variável sinalizadora manterá 1 se houver uma troca, senão ela sairá do loop. Abaixo está o programa de classificação de bolhas otimizado em C.

#include<stdio.h>

vazio principal

{

int array [10], i, j, num, flag=0;

para (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

for(i=0;i<=9;i++)

{

for(j=0;j<=9-i;j++)

{

if(matriz[j]>matriz[j+1])

{

num= array[j];

matriz[j]=matriz[j+1];

matriz[j+1]=num;

bandeira=1;

}

if(! sinalizador)

{

pausa;

}

}

}

printf("A matriz ordenada é /n");

for(i=0;i<=9;i++)

{

printf("%d",&array[i])

}

}

O programa fornecido é executado de maneira semelhante ao programa normal de classificação de bolhas. A única mudança é o uso da variável flag. Inicialmente, o sinalizador é definido como 0. No entanto, se ocorrer uma troca, o sinalizador se torna 1. Isso implica que o array ainda requer mais uma verificação. Por outro lado, se o sinalizador não for 1, implicando que a troca não ocorreu, saímos do loop interno, assumindo que o array já está ordenado. Uma vez executado, obteremos o mesmo resultado que o Bubble sort normal.

Complexidade de tempo

A complexidade de tempo do melhor caso para a ordenação por bolha é O(n). Isso acontece quando o array já está ordenado. O pior caso é O(n*n) quando o array não foi ordenado.

Leia: Os 12 principais programas de padrão em Java que você deve fazer check-out hoje

Qual o proximo?

Se você estiver interessado em aprender mais sobre Java, desenvolvimento de software full-stack, confira o PG Diploma in Full-stack do upGrad & IIIT-B, projetado para profissionais que trabalham e oferece mais de 500 horas de treinamento rigoroso, mais de 9 projetos , e atribuições, status de ex-alunos do IIIT-B, projetos práticos práticos e assistência de trabalho com as principais empresas.