Objectivo:
Neste método devemos inserir os
elementos nas suas posições correctas. Escolhemos um elemento e colocamos-o na
sua posição correcta deslocando os elementos que estão em posições incorrectas.
Exemplo:
l->25 57 48 37 12 92 86 33
25 57
25 48 57
25 37 48 57
12 25 37 48 57
12 25 37 48 57 92
12 25 37 48 57 86 92
12 25 33 37 48 57 86 62
Algortimo:
insercao
(l->lista)->lista
se evazia(l)
devolve NULL
senao
devolve inserir_ord(cabeca(l),insercao(proximo(l)))
selecção
Objectivo:
Este
método consiste em encontrar repetidamente o menor elemento e colocá-lo na sua
devida posição.
Exemplo:
l->25 57
48 37 12 92 86 33
25
57 48 37 12 33 86 92
25 57 48 37 12 33 86 92
25 33 48 37 12 57 86 92
25 33 12 37 48 57 86 92
25 33 12 37 48 57 86 92
25 12 33 37 48 57 86 92
12 25 33
37 48 57 86 92
Algoritmo:
seleccao(l->lista)->lista
se evaz(l)
devolve null
senao
devolve cons(min(l),
seleccao(eliminar(a,l)))
bolha (Bubble sort)
Objectivo:
A ideia básica do Bubble Sort é percorrer os dados sequencialmente várias vezes. Em cada passagem pelos dados devemos comparar cada elemento com o seu sucessor. Se os elementos não e ordenados devemos trocá-los de posição.
Exemplo:
l -> 25 57 48 37 12 92 86 33
25 48 37 12 57 86 33 92
25 37 12 48 57 33 86 92
25 12 37 48 33 57 86 92
12 25 37 33 48 57 86 92
12 25 33 37 48 57 86 92
12 25 33 37 48 57 86 92
12 25 33 37 48 57 86 92
Algoritmo:
trocar(l->lista,
bool->boolean)->lista
se evaz(l)
devolve NULL
senao
se evaz(proximo(l)
devolve l
senao
se cabeca(l)>cabeca(proximo(l))
bool=verdadeira
devolve cons(cabeca(proximo(l)),trocar (cons(cabeca(l),
proximo(proximo(l))),bool)
senao
devolve cons (cabeca (l), trocar
(proximo(l), bool))
Bolha (l->lista)
B=falso
trocar (l,B)
se B
bolha (l)
16386 Luis Martins