Prévia do material em texto

ANÁLISE DE ALGORITMOS
Selection Sort consiste em ordenar a lista “selecionando” a cada iteração o menores itens possíveis e os colocando da esquerda para a direita. É necessário para cada item da lista percorrê-la toda (logo, serão necessários dois loops: um para cada elemento da lista e outro para cada um desses elementos percorrer toda a lista).
Suas principais vantagens estão na fácil implementação do algoritmo, além de ocupar pouca memória se comparado a algoritmos como quick e merge sort.
Desempenho
Dado uma lista de seis posições [6,5,4,3,2,1]:
Serão inicialmente cinco comparações (ou 6–1) para o processo de seleção obter o menor item (o item que está sendo iterado (no caso índice 0) não precisa ser comparado. Logo, conta-se do segundo ao sexto item, ou seja dos índices 1 a 5: 1, 2, 3, 4, 5) e assim por diante.
Pode-se expressar isso então, da seguinte forma:
[(6–1) + (6–5)] + [(6–2) + (( 6 - 4)] + [(6–3)] = 15
A fórmula para calcular o número de operações no selection sort é:
n *[(n — 1) / 2]
Desse jeito, podemos observar que para cada acréscimo na lista de elementos aumentamos o número de operações:
4 * 1,5 = 6
5 * 2 = 10
6 * 2,5 = 15
7 * 3 = 21
500 * 249,5 = 124750