Algoritmos III

Enviado por Tiago Madeira


1. Ordenação por Seleção

Hoje vou apresentar mais um algoritmo de ordenação de vetores. É a Ordenação por Seleção (ou Selection Sort). Sem mais papo e antes mesmo da explicação, vamos ao seu pseudocódigo:

1. para i 1 até tamanho-1, faça

2. minimo i

3. para j i+1 até tamanho, faça

4. se vetor[j] < vetor[minimo], então

5. minimo j

6. fim-se

7. fim-para

8. temp vetor[i]

9. vetor[i] vetor[minimo]

10. vetor[minimo] temp

11. fim-para

tamanho = comprimento do vetor

Funcionamento

A idéia é sempre procurar o menor elemento do vetor e inseri-lo no início do vetor. Procuramos o menor valor do vetor e colocamos ele em vetor[1]. Procuramos o menor valor do vetor excluindo o já colocado e colocamos ele em vetor[2]. E assim vamos indo até termos todo o vetor ordenado.

Partindo sempre a partir do último elemento reordenado (a partir do i), o programa procura o menor elemento no vetor e o substitue pelo elemento i atual.

Exemplo de Funcionamento

O programa recebe o seguinte vetor.

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

5

3

7

8

2

5

Aí ele começa com . Vou sempre marcar com a cor preta e com a cor cinza.

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

5

3

7

8

2

5

Ele marca o próprio índice i como a variável minimo, que é sempre o menor elemento do vetor. Então, ele faz um para de até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

... , portanto .

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

5

3

7

8

2

5

... , portanto não mexemos em nada.

... , portanto não mexemos em nada.

... , portanto .

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

5

3

7

8

2

5

... , portanto não mexemos em nada.

Agora substituímos o v[minimo] pelo v[i], formando com isto o novo vetor:

v[1]

v[2]

v[3]

v[4]

v[5]

v[6]

2

3

7

8

5

5

E assim vamos fazendo com os outros elementos até que todo o vetor esteja ordenado.

Custo

Este algoritmo não tem um melhor/pior caso, porque todos os elementos são varridos, sempre. Medir seu custo é simples. Custo de linha por linha...

n = tamanho do vetor

  1. ???

Você pode estar se perguntando porque eu coloquei este custo para a linha 5. Afinal, a linha 5 diria que este programa tem um melhor/pior caso, porque ela não seria executada se o se retornar falso. Mas o caso é que ela é desprezível. Uma soma como estas para o custo geral do nosso algoritmo não vai influenciar em nada. Quer ver? Vamos somar os custos com esta linha valendo (como se nenhum se entrasse) e depois com ela valendo .

Primeiro cálculo

Segundo cálculo

Conclusão

Como vocês puderam ver, não faz diferença alguma o que aquela somatória nos proporciona. Já que todo o cálculo de algoritmos é baseado apenas no maior expoente de n e desprezamos todas as constantes (inclusive as que multiplicam o n de maior expoente, muitos passos são desprezíveis.

2. Mini-Poker

Este artigo é o nono da Série Algoritmos. Se você ainda não leu os artigos anteriores, sugiro que leia antes de continuar:


Página seguinte 



As opiniões expressas em todos os documentos publicados aqui neste site são de responsabilidade exclusiva dos autores e não de Monografias.com. O objetivo de Monografias.com é disponibilizar o conhecimento para toda a sua comunidade. É de responsabilidade de cada leitor o eventual uso que venha a fazer desta informação. Em qualquer caso é obrigatória a citação bibliográfica completa, incluindo o autor e o site Monografias.com.