Questão Q154721

Question

O algoritmo Bubble Sort é popular, mesmo que ineficiente. Usando-se esse algoritmo para ordenar uma tabela, alocada sequencialmente, em ordem crescente contendo os números [5, 4, 1, 3, 2] serão feitas:

Answer

Estrutura do Algoritmo

vetor = { 5, 4, 1, 3, 2 }

para i de 1 até 5
para j de i+1 até 5
se ( vetor[i] > vetor[j] ) então
troque ( vetor[i], vetor[j] )

Algorito em tempo de execução

para i=1
5 > 4 (troca), 4 > 1 (troca), 1 > 3, 1 > 2
vetor = { 1, 5, 4, 3, 2 }

para i=2
5>4(troca), 4>3(troca),3>2(troca)
vetor = { 1,2,5,4,3)

para i=3
5>4(troca), 4>3(troca)
vetor = {1,2,3,5,4}
para i=4
5>4(troca)
vetor = {1,2,3,4,5}

10 comparações e 8 trocas

Answer

Comparações x trocas:
5 4 1 3 2 (troca)
4 5 1 3 2 (troca)
4 1 5 3 2 (troca)
1 4 5 3 2 (troca)
1 4 3 5 2 (troca)
1 3 4 5 2 (Não Troca)
1 3 4 5 2 (troca)
1 3 4 2 5 (troca)
1 3 2 4 5 (troca)
1 2 3 4 5 (Não Troca)

Answer

[5, 4, 1, 3, 2] - Array Original

[5, 4, 1, 3, 2] - Compara 1 e [4, 5, 1, 3, 2] - Troca 1
[4, 5, 1, 3, 2] - Compara 2 e [4, 1, 5, 3, 2] - Troca 2
[4, 1, 5, 3, 2] - Compara 3 e [4, 1, 3, 5, 2] - Troca 3
[4, 1, 3, 5, 2] - Compara 4 e [4, 1, 3, 2, 5] - Troca 4
[4, 1, 3, 2, 5] - Compara 5 e [1, 4, 3, 2, 5] - Troca 5
[1, 4, 3, 2, 5] - Compara 6 e [1, 3, 4, 2, 5] - Troca 6
[1, 3, 4, 2, 5] - Compara 7 e [1, 3, 2, 4, 5] - Troca 7
[1, 3, 2, 4, 5] - Compara 8 e Não troca - Troca 7
[1, 3, 2, 4, 5] - Compara 9 e [1, 2, 3, 4, 5] - Troca 8
[1, 2, 3, 4, 5] - Compara 10 e Não troca - Troca 8

Fim

Para mais estudos: http://www.youtube.com/watch?v=P00xJgWzz2c

Answer

Bubble sorte, ordenação por flutuação, é um algoritmo de ordenação dos mais simples. Percorre o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. No melhor caso executa n²operações relevantes, onde n representa o número de elementos do vetor. No pior caso também são feitas n² operações. A complexidade é de ordem quadrática e por isso ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Answer

[5, 4, 1, 3, 2] - Array Original

A forma correta que o algoritmo funciona é a seguinte:

[5, 4, 1, 3, 2] - Compara 1 e [4, 5, 1, 3, 2] - Troca 1

[4, 5, 1, 3, 2] - Compara 2 e [1, 5, 4, 3, 2] - Troca 2

[1, 5, 4, 3, 2] - Compara 3 e não troca

[1, 5, 4, 3, 2] - Compara 4 e não troca

[1, 5, 4, 3, 2] - Compara 5 e [1, 4, 5, 3, 2] - Troca 3

[1, 4, 5, 3, 2] - Compara 6 e [1, 3, 5, 4, 2] - Troca 4

[1, 3, 5, 4, 2] - Compara 7 e [1, 2, 5, 4, 3] - Troca 5

[1, 2, 5, 4, 3] - Compara 8 e [1, 2, 4, 5, 3] - Troca 6

[1, 2, 4, 5, 3] - Compara 9 e [1, 2, 3, 5, 4] - Troca 7

[1, 2, 3, 5, 4] - Compara 10 e [1, 2, 3, 4, 5] - Troca 8

Answer

Para mim a resposta correta seria:

4,5,1,3,2 (1 troca e 1 comparação)

4,1,5,3,2 (2 troca e 2 comparação)

4,1,5,2,3 (3 troca e 3 comparação)

1,4, 5,2,3 (4 troca e 4 comparação)

1,4,5,2,3 (4 troca e 5 comparações)

1,4,2,5,3 (5 troca e 6 comparação)

1,4,2,3,5 ( 6 troca e 7 comparação)

1,4,2,3,5 (6 troca e 8 comparação)

1,2,4,3,5 (7 troca e 9 comparação)

1,2,3,4,5 (8 troca e 10 comparação)

1,2,3,4,5 (8 troca e 11 comparação)

1,2,3,4,5 (8 troca e 12 comparação)

1,2,3,4,5 (8 troca e 13 comparação)

1,2,3,4,5 (8 troca e 14 comparação)

O algoritmo na (8 troca e 10 comparação) não sabe se os anteriores estão ordenados, desta forma, ele precisará percorrer a lista mais uma vez.

Answer

a-

inicio: 5,4,1,3,2

4,5,1,3,2

4,1,5,3,2

4,1,3,5,2

4,1,3,2,5

1,4,3,2,5

1,3,4,2,5

1,3,2,4,5

1,2,3,4,5

_________________________________________________________________________________________________________

o n° comparacoes segue formato round-robin: (n)²-n/2. 4 itens: 6 comp. 5 itens: 10 comp

SóProvas

Continue usando...

O que está incluso