SELECTION SORT

Algoritmo de Ordenação por Seleção – Selection
Sort
Material preparado por:
Prof. Augusto Mendes Gomes Jr.
Prof. Marisa Ortegoza da Cunha

Descrição
Neste algoritmo, o vetor é varrido, da esquerda para a direita, deslocando, a cada iteração, o menor elemento para a extremidade da esquerda.
Este algoritmo seleciona sempre, a cada iteração, o menor elemento remanescente do conjunto não ordenado e move este elemento para sua posição correta. Algoritmo
1.
2.

Encontrar o menor elemento e trocar com o elemento na primeira posição do vetor
Encontrar o segundo menor elemento e trocar com o elemento na segunda posição do vetor, e assim sucessivamente ...

Exemplo
Entrada:
1a. iteração:
2a. iteração:
3a. iteração:
4a. iteração:
5a. iteração:
6a. iteração:
7a. iteração:
Saída:

[13, 10, 5, 8, 9, 7, 6, 8]
[5, 10, 13, 6, 8, 9, 7, 8]
[5, 6, 13, 10, 8, 9, 7, 8]
[5, 6, 7, 10, 8, 9, 13, 8]
[5, 6, 7, 8, 10, 9, 13, 8]
[5, 6, 7, 8, 8, 9, 13, 10]
[5, 6, 7, 8, 8, 9, 13, 10]
[5, 6, 7, 8, 8, 9, 10, 13]
[5, 6, 7, 8, 8, 9, 10, 13]

Algoritmo
Entrada: vetor X[1 .. N]
1
2
3
4
5
6
7
8
9
10

para i = 1 até n - 1 faça { menor = i; para j = i + 1 até n faça { se (X[menor] > X[j]) então menor = j;
}
aux = X[i];
X[i] = X[menor];
X[menor] = aux;
}

Complexidade
Entrada: vetor X[1 .. N]
1 para i = 1 até n - 1 faça {
2
menor = i;
3
para j = i + 1 até n faça {
4
se (X[menor] > X[j]) então
5
menor = j;
6
}
7
aux = X[i];
8
X[i] = X[menor];
9
X[menor] = aux;
10 }

Custo
?
?
?
?
?
?
?
?

Melhor Caso
O melhor caso ocorre quando?

Pior Caso
O pior caso ocorre quando?

Exercício
Implemente o algoritmo do Selection Sort para fazer a ordenação, percorrendo o vetor da direita para a esquerda, colocando, a cada iteração, o maior elemento para a última posição do vetor remanescente.
Fale a sua complexidade no pior e no melhor
caso.