O método de ordenação simples Bubblesort é conhecido por apresentar o pior desempenho entre todos os métodos de ordenação. Isso ocorre devido ao grande número de comparações que esse método efetua, independentemente da distribuição de dados do vetor (totalmente desordenado, pré-ordenado ou até ordenado).
No entanto, esse método pode ser ligeiramente melhorado para alcançar resultados um pouco melhores.
Com base nisso, dado o algoritmo Bubblesort apresentado, resolva as seguintes atividades:
Elabore e descreva uma estratégia que pode ser empregada no método Bubblesort para melhorar seu desempenho.
Implemente essa melhoria no algoritmo Bubblesort visando reduzir seu tempo de processamento.
Para o vetor dado, esse algoritmo realiza 10 comparações e ordena o vetor com 2 trocas.
Uma estratégia que pode ser empregada no método Bubblesort é comparar o elemento atual, no laço de repetição interno, apenas com o próximo elemento do vetor, ao invés de compará-lo com todos os elementos subsequentes. Isso faz com que seja possível identificar se não existem mais trocas a serem realizadas, evitando comparações desnecessárias.
Para o mesmo vetor, o algoritmo Buublesort melhorado realiza sete comparações e duas trocas, reduzindo o número de comparações, nesse caso, em 30%.
Algoritmo Bubblesort melhorado:
1 votes Thanks 1
fabiocn21
preciso do algoritmo melhorado, você teria ?
fabiocn21
tem o algoritmo pra postar na resposta ?
Lista de comentários
Resposta:
Explicação:
Uma estratégia que pode ser empregada no método Bubblesort é comparar o elemento atual, no laço de repetição interno, apenas com o próximo elemento do vetor, ao invés de compará-lo com todos os elementos subsequentes. Isso faz com que seja possível identificar se não existem mais trocas a serem realizadas, evitando comparações desnecessárias.
Para o mesmo vetor, o algoritmo Buublesort melhorado realiza sete comparações e duas trocas, reduzindo o número de comparações, nesse caso, em 30%.
Algoritmo Bubblesort melhorado:
Resposta:
Padrão de resposta esperado
A resposta é:
algoritmo "Bolha Modular"
var
valores:vetor[0..3] de real
aux:real
procedimento ler()
var
i:inteiro
inicio
para i de 0 ate 3 faca
escreval("digite o ", i+1,"º numero")
leia (valores[i])
fimpara
fimprocedimento
procedimento classificar()
var
i,
j:inteiro
inicio
para i de 0 ate 3 faca
para j de 0 ate 3 faca
se valores[i] > valores[j] entao
aux <- valores[j]
valores[j] <- valores[i]
valores[i] <- aux
fimse
fimpara
fimpara
fimprocedimento
procedimento mostrar()
var
i: inteiro
inicio
para i de 0 ate 3 faca
escreval(valores[i])
fimpara
fimprocedimento
inicio
ler()
classificar()
mostrar()
fimalgoritmo
Explicação: