Escola Secundária da Boa Nova 2013
Aplicações informáticas – Ensino da programação
Sumário: Algoritmos de ordenação – Ordenação por seleção.
Implementação do algoritmo de ordenação por seleção no Scratch.
Objetivos:
•
•
•
•
Esclarecer porque são usados os algoritmos de ordenação
Definir o que é a ordenação
Esclarecer como é feita a ordenação utilizando o algoritmo de seleção
Implementar o algoritmo de ordenação por seleção no Scratch;
• Em vários momentos do dia a dia, deparamo-nos com a necessidade de consultar
dados ordenados. Vamos tomar como exemplo uma lista telefónica. Imaginem
como seria consultar o telefone de alguém se os nomes não estivessem ordenados
por ordem alfabética.
• Uma das atividades mais utilizada na computação é a ordenação.
• As ordenações mais utilizadas são as numéricas e as alfabéticas.
• Existem diversos algoritmos para ordenação. Nesta aula será apresentada a
implementação do algoritmo de seleção
“Ordenar corresponde ao processo de rearranjar um conjunto de objetos
em ordem ascendente ou descendente. O objetivo principal da ordenação
é facilitar a recuperação posterior de itens do conjunto ordenado. ...A
atividade de colocar as coisas em ordem está presente na maioria das
aplicações em que os objetos armazenados têm de ser pesquisados e
recuperados...”
Nivio Ziviani. Projeto de Algoritmos com implementação em C++ e Java.
THOMSON Learning, São Paulo, 1st edition, 2007
Provavelmente é o algoritmo mais
intuitivo:
– Encontrar o mínimo da lista
– Trocar com o primeiro elemento
– Continuar para os restantes
elementos da lista (excluindo o
primeiro)
5
4
7
10
2
2
4
7
10
5
2
4
7
10
5
2
4
5
10
7
2
4
5
7
10
Para i desde 1 até N-1 fazer:
pos_min
i
Para j desde i+1 até N fazer:
Se (Lista[j] < Lista[pos_min]) entao
pos_min
j
Se Lista[pos_min] > Lista[i], troca os conteúdos da seguinte forma:
aux
V[pos_min]
V[pos_min]
V[i]
V[i]
aux
Cria um programa no Scratch
que permita ordenar os
dados de uma lista de valores
numéricos por ordem
crescente.
Dicas:
• Apenas podes ter uma lista de valores
(poupar memória!)
• Cria duas variáveis uma para guardar o
mínimo e outra auxiliar para efetuar a
troca dos valores
• Vais ter de dois ciclos um dentro do
outro, pelo que necessitas de dois
contadores: i,j
• No início inicia o relógio de forma a
registares quanto tempo demora o
algoritmo a ordenar os valores
No final envia para a Moodle a lista
ordenada com o nome de ficheiro:
lista_selecao_nome_numero.sb