Apresentação select sort .pdf

Prévia do material em texto

Selection Sort
Ordenação por seleção
Bruno Luiz Oliveira Campos
Camila Silva Peixoto
Carla Regina Gomes de Aguiar
Dryelle Rodrigues de Freitas
Marilana Gabriela Urzêdo Oliveira
Selection Sort
Introdução:
A ordenação por seleção, como
também é chamada, é um algoritmo
de ordenação que consiste em passar
sempre o menor valor da lista para a
primeira posição, depois, o de
segundo menor valor para a segunda
posição, e assim sucessivamente com
os (n-1) elementos restantes, até os
últimos dois elementos.
2
3
Implementação:
A seguir, temos exemplos em
relação à lógica de seleção de
ordenação, com o objetivo de
ordenar os dados de maneira
crescente, formando laços de
repetição aninhados.
4
5
Exemplo:
6
7
Análise da complexidade
O Selection Sort compara a cada 
interação um elemento com os outros, 
visando encontrar o menor. Dessa 
forma, podemos entender que não existe 
um melhor caso mesmo que o vetor 
esteja ordenado ou em ordem inversa 
serão executados os dois laços do 
algoritmo, o externo e o interno. A 
complexidade deste algoritmo será 
sempre O(n²).
8
Exemplo:
9
Vantagens
• Algoritmo de simples implementação, recomendado
para pequenos conjuntos de dados;
• Não necessita de um vetor auxiliar.
• Por não usar um vetor auxiliar para realizar a 
ordenação, ele ocupa menos memória.
• Ele é uns dos mais velozes na ordenação de vetores 
de tamanhos pequenos.
10
Desvantagens
• Ele é um dos mais lentos para vetores de tamanhos 
grandes.
• Ele não é estável.
• Ele faz sempre n² comparações, independente do 
vetor está ordenado ou não.
11
Aplicações
• Este é um algoritmo a ser utilizado para tabelas
com poucos registros.
• O fato da tabela já estar ordenada não ajuda em
nada pois o custo continua quadrático.
• Este é um exemplo de um método não estável,
pois ele nem sempre deixa os registros com
chaves iguais na mesma posição relativa.
12
13
Bibliografia
• ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos
de. Estruturas de dados: algoritmos, análise da complexidade
e implementações em JAVA e C/C++. São Paulo - Sp: Pearson
Education - Br, 2011. 432 p.
• www.toptal.com/developers/sorting-algorithms/selection-sort
Acesso dia 10/12/2016
14