Seja o pseudo-código abaixo do Bubble Sort:

para i = n até 2 faça
       para j = 1 até i-1 faça
              se(valor[j] > valor[j+1])
                     troca(valor[j], valor[j+1])
              fim-se
       fim-para
fim-para

quando i = n, j varia de 1 até n-1 --> no máximo n-1 trocas
quando i = n-1, j varia de 1 até n-2 --> no máximo n-2 trocas
...
quando i = 2, j varia de 1 até 1 --> no máximo 1 troca

Máximo de trocas = (n-1 + n-2 + ... + 1) = (n-1 + 1)*(n-1)/2 =
n*(n-1)/2 (Progressão Aritmética)

Para n = 10, n*(n-1)/2 = 10*9/2 = 45

As estruturas de laço e a condição de troca podem variar com a
implementação, mas o Bubble Sort sempre será da ordem O(n^2).

Lista: (8,6,10,7,5)

Varredura 1:
(8,6,10,7,5) troca posições 1,2
(6,8,10,7,5) não troca posições 2,3
(6,8,10,7,5) troca posições 3,4
(6,8,7,10,5) troca posições 4,5
(6,8,7,5,10)

Varredura 2:
(6,8,7,5,10) não troca posições 1,2
(6,8,7,5,10) troca posições 2,3
(6,7,8,5,10) troca posições 3,4
(6,7,5,8,10)

Varredura 3:
(6,7,5,8,10) não troca posições 1,2
(6,7,5,8,10) troca posições 2,3
(6,5,7,8,10)

Varredura 4:
(6,5,7,8,10) troca posições 1,2
(5,6,7,8,10)

4 varreduras.

2011/9/7 arkon <ar...@bol.com.br>:
> Alguém pode dar uma forcinha?
>
> Para colocar em ordem crescente uma lista de n números reais, será utilizado
> o algoritmo conhecido como Bubblesort, que consiste em comparar elementos
> consecutivos da lista, trocando os mesmos de posição se o número da esquerda
> for maior. O processo se inicia da esquerda para a direita. A primeira
> varredura da lista coloca o maior elemento da lista na sua posição
> definitiva. A segunda varredura da lista se faz com a sublista obtida da
> primeira excluindo o último elemento, e assim sucessivamente. Com base nessa
> exposição, julgue os itens subsequentes.
>
> (1) Se n=10, o número de trocas efetuadas será menor ou igual a 45.
> (2) Se a lista é (8,6,10,7,5), será necessárias 3 varreduras para ordenar a
> lista.
>
> Gab.: C, E.
> =========================================================================
> Instru�ões para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================



-- 
Henrique

=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================

Responder a