O programa a seguir, em Python, implementa o algoritmo do mé...
O programa a seguir, em Python, implementa o algoritmo do método de bolha, imprimindo o resultado de cada passo.
Qual será a quarta linha impressa para a chamada bolha([ 4, 3, 1, 9, 8, 7, 2, 5]) ?
A bolha verifica se cada elemento da posição i é maior que o próximo (i+1). Se for maior, trocam de lugar, se não, não trocam. O "i" será o 1º número, depois o 2º, depois o 3º... no exemplo abaixo, primeiro o i = 4 (1º número), e por isso trocarão de lugar. Ato contínuo, o i = 4 novamente, porque 4 trocou de lugar com 3 e agora é o 2º número. E assim sucessivamente.
[4, 3, 1, 9, 8, 7, 2, 5] - 4 é maior que 3, sim. Troca de lugar → [3, 4, 1, 9, 8, 7, 2, 5]
[3, 4, 1, 9, 8, 7, 2, 5] - 4 é maior que 1, sim. Troca de lugar → [3, 1, 4, 9, 8, 7, 2, 5]
[3, 1, 4, 9, 8, 7, 2, 5] - 4 é maior que 9, não. Não troca → [3, 1, 4, 9, 8, 7, 2, 5]
[3, 1, 4, 9, 8, 7, 2, 5] - 9 é maior que 8, sim. Troca de Lugar → [3, 1, 4, 8, 9, 7, 2, 5]
[3, 1, 4, 8, 9, 7, 2, 5] - 9 é maior que 7, sim. Troca de Lugar → [3, 1, 4, 8, 7, 9, 2, 5]
[3, 1, 4, 8, 7, 9, 2, 5] - 9 é maior que 2, sim. Troca de Lugar → [3, 1, 4, 8, 7, 2, 9, 5]
[3, 1, 4, 8, 7, 2, 9, 5] - 9 é maior que 5, sim. Troca de Lugar → [3, 1, 4, 8, 7, 2, 5, 9]
Linha 1: [3, 1, 4, 8, 7, 2, 5, 9]
E assim segue o raciocínio, basta ir comparando "i" com o próximo número e trocando de lugar se o número seguinte for menor:
Linha 2: [1, 3, 4, 7, 2, 5, 8, 9]
Linha 3: [1, 3, 4, 2, 5, 7, 8, 9]
Linha 4: [1, 3, 2, 4, 5, 7, 8, 9]
A bolha (bubble sort) é o algoritmo mais simples, mas o menos eficiente, pois pode ser ineficiente para listas muito grandes.
Flávio Diniz, por que a primeira linha do teu esquema é o último resultado da alternância dos números dados inicialmente na questão?
Vejamos:
def bolha(lista):
#a lista contém [ 4, 3, 1, 9, 8, 7, 2, 5] , 8 itens
for passo in range(len(lista)-1,0,-1):
# dado o 'len(lista)-1,0,-1' aqui, 'passo' recebe valores do 7 ao 0 (8-1);
for i in range(passo):
# 'i' recebe os valores em 'passo', que são (7,6,5,4,3,2,1,0)
if lista[i]>lista[i+1]:
# compara valores da lista conforme o valor corrente de 'i'. por exemplo:
# lista[6] >lista[7] = 2>5? se a resposta for 'sim', executa a próxima linha
lista[i],lista[i+1]=lista[i+1],lista[i]
# isso aqui acaba mudando os valores de um pelo outro, criando ordem crescente
print(lista)
Rodei o código e deu:
def bolha(lista):
for passo in range(len(lista)-1,0,-1):
for i in range(passo):
if lista[i]>lista[i+1]:
lista[i],lista[i+1] = lista[i+1],lista[i]
print(lista)
[3, 1, 4, 8, 7, 2, 5, 9]
[1, 3, 4, 7, 2, 5, 8, 9]
[1, 3, 4, 2, 5, 7, 8, 9]
[1, 3, 2, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
def bolha(lista):
___for passo in range(len(lista)-1,0,-1):
______for i in range(passo):
_________print(i)
_________print(lista[i], lista[i+1])
_________if lista[i]>lista[i+1]:
____________lista[i], lista[i+1] = lista[i+1], lista[i]
______print(lista) bolha([ 4, 3, 1, 9, 8, 7, 2, 5])
0 valor de ' i '
4 3 valor da lista[i] lista[i+1]
1 valor de ' i '
4 1 valor da lista[i] lista[i+1]
2 valor de ' i '
4 9 valor da lista[i] lista[i+1]
3 valor de ' i '
9 8 valor da lista[i] lista[i+1]
4 valor de ' i '
9 7 valor da lista[i] lista[i+1]
5 valor de ' i '
9 2 valor da lista[i] lista[i+1]
6 valor de ' i '
9 5 valor da lista[i] lista[i+1]
[3, 1, 4, 8, 7, 2, 5, 9] 1º L
0 valor de ' i '
3 1 valor da lista[i] lista[i+1]
1 valor de ' i '
3 4 valor da lista[i] lista[i+1]
2 valor de ' i '
4 8 valor da lista[i] lista[i+1]
3 valor de ' i '
8 7 valor da lista[i] lista[i+1]
4 valor de ' i '
8 2 valor da lista[i] lista[i+1]
5 valor de ' i '
8 5 valor da lista[i] lista[i+1]
[1, 3, 4, 7, 2, 5, 8, 9] 2º L
0 valor de ' i '
1 3 valor da lista[i] lista[i+1]
1 valor de ' i '
3 4 valor da lista[i] lista[i+1]
2 valor de ' i '
4 7 valor da lista[i] lista[i+1]
3 valor de ' i '
7 2 valor da lista[i] lista[i+1]
4 valor de ' i '
7 5 valor da lista[i] lista[i+1]
[1, 3, 4, 2, 5, 7, 8, 9] 3º L
0 valor de ' i '
1 3 valor da lista[i] lista[i+1]
1 valor de ' i '
3 4 valor da lista[i] lista[i+1]
2 valor de ' i '
4 2 valor da lista[i] lista[i+1]
3 valor de ' i '
4 5 valor da lista[i] lista[i+1]
[1, 3, 2, 4, 5, 7, 8, 9] 4º L
0
1 3
1
3 2
2
3 4
[1, 2, 3, 4, 5, 7, 8, 9]
0
1 2
1
2 3
[1, 2, 3, 4, 5, 7, 8, 9]
0
1 2
[1, 2, 3, 4, 5, 7, 8, 9]
Então, coloquei os comandos abaixo, para descobrir qual o valor de ' i ' que o programa estava executando:
_________print(i)
_________print(lista[i], lista[i+1])
Sabendo que, os valores possíves de ' i ' são os regados pelo range abaixo
range(len(lista)-1,0,-1)
range(8-1,0,-1)
range(7,0,-1)
[7,6,5,4,3,2,1]
Porém, observa-se que o programa está para usando ' i ' os valores [0,1,2,3,4,5,6] ao invés dos gerados pelo range(len(lista)-1,0,-1)
Alguém poderia me explicar, o que não não consegui entender ?
Obrigado.
ei nesse caso é preciso criar uma lista para chamar a função ?
Questão demorada. Se perder a concentração, já era
Não precisa fazer todas as 4 iterações para marcar o item: no bubble sort os valores maiores podem andar mais de uma posição "para frente", mas os valores menoress só podem andar uma para trás por iteração.
Analisando o item A, ele não pode acontecer, pois estamos criando uma ordem crescente, não faz sentido a posição do "3".
No item C, não pode ser pois o "2" teria movido 5 posições em 4 iterações. Aí você percebe que o "2" necessariamente sofreu 4 swaps, indo pra terceira posição, e só o item D reflete isso.
Por que pulei o item B na análise? Porque você começa analisando as diferenças nos itens:
No Item A o primeiro elemento é o "3", faz sentido? Não
No Item C o segundo elemento é o "2", faz sentido? Não, mas gera uma linha de pensamento:
Onde estará o elemento "2" na quarta iteração? R: No terceiro valor do array. Item D.
Gabarito: D. Nível altíssimo! A persistência leva ao êxito! Nunca perca a fé!
[3, 1, 4, 8, 7, 2, 5, 9]
[1, 3, 4, 7, 2, 5, 8, 9]
[1, 3, 4, 2, 5, 7, 8, 9]
[1, 3, 2, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 7, 8, 9]
lista = [4, 3, 1, 9, 8, 7, 2, 5]
def bubble(list):
for step in range(len(lista)-1, 0, -1):
for i in range(step):
if lista[i] > lista[i+1]:
lista[i], lista[i+1] = lista[i+1], lista[i]
print(lista)
bubble(lista)
escriturário!?