Hoje veremos o método de ordenação conhecido por ordenação por seleção, ou "selection sort" em inglês.
Neste método pegamos o menor valor entre todos os elementos da matriz e o trocamos pelo primeiro elemento. Depois procuramos o menor entre o segundo e o último elemento da matriz e o trocamos pelo segundo elemento. Deepois procuramos o menor valor entre o terceiro e o último elemento da matriz e o trocamos pelo terceiro, e assim por diante.
Para melhor ilustrar este método vamos usar o mesmo vetor que usamos no post anterior:
|
4 |
5 |
1 |
3 |
2 |
Primeiro identificamos o menor valor, no caso 1:
|
4 |
5 |
1 |
3 |
2 |
e o trocamos pelo primeiro elemento:
|
1 |
5 |
4 |
3 |
2 |
Nosso primeiro elemento do vetor, já é o menor de todos.
Agora identificamos o menor valor entre o segundo e o último elemento do vetor:
| 2 é o menor valor entre o segundo e o último elemento do vetor | ||||
|
1 |
5 |
4 |
3 |
2 |
e o trocamos pelo segundo elemento:
|
1 |
2 |
4 |
3 |
5 |
Depois identificamos o menor valor entre o terceiro e o último elemento do vetor:
| 3 é o menor valor entre o terceiro e o último elemento do vetor | ||||
|
1 |
2 |
4 |
3 |
5 |
e trocamos pelo terceiro elemento:
|
1 |
2 |
3 |
4 |
5 |
E temos nosso vetor ordenado.
Um algoritmo para este problema de ordenação seria:
INÍCIO
DECLARAÇÃO DE VARIÁVEIS
inteiro: V(n);
inteiro: n;
inteiro: contador1;
inteiro: contador2;
inteiro: indice_menor;
inteiro: menor;
ENTRADA DE DADOS
ler n;
ler V(n);
PROCESSAMENTO
para contador1 de 1 até (n - 1) incremento 1 faça
indice_menor <== contador1;
menor <== V(contador1);
para contador2 de (contador1 + 1) até n incremento 1 faça
se V(contador2) < menor
indice_menor <== contador2;
menor <== V(indice_menor);
V(indice_menor) <== V(contador1);
V(contador1) <== menor;
fimse;
fimpara;
fimpara;
SAÍDA DE DADOS
exibir V(n);
FIM
Abaixo temos uma codificação Python que resolve o problema:
#!/usr/bin/python
# -*- coding: iso-8859-1 -*-
# selection-sort.py
# Ordenação pelo método da seleção
def verificaMenor(lista):
m = lista[1]
for c in lista:
if c < m:
m = c
return m
l = [4,5,1,2,3]
for i in range(len(l) - 1):
m = verificaMenor(l[i:])
l[l.index(m)] = l[i]
l[i] = m
print l
A única observação no código acima é que criei a função "verificaMenor()" para facilitar as coisas.
Codifique em C e compare com o código Python. Tenho certeza que você achará que com Python as coisas são bem mais fáceis de fazer.
Um grande abraço e bons estudos.
Samuel