ppt gnomesort

Prévia do material em texto

Gnome Sort
Blumenau
2017
O que é?
Metodo de Ordenação similar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia grande de trocas assim como o Bubble sort.
Como Funciona?
O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
Na Prática
Vantagens
Fácil Implementação
 Algoritmo Estável
 Bom desempenho em listas pequenas
Desvantagens
Número grande de movimentações
 Não possui desempenho bom para listas grandes
Implementação
function gnomeSort(a[0..size-1])
 i := 1
 j := 2
 while i < size do
 if a[i-1] <= a[i] then
 // for descending sort, use >= for comparison
 i := j
 j := j + 1 
 else
 swap a[i-1] and a[i]
 i := i - 1
 if i = 0 then
 i := j
 j := j + 1
 endif
 endif
 done
Conclusão
Entendemos que esse método se encaixa para poucos arrays, pois acreditamos que o mesmo não teria um bom desempenho para grandes arrays devido às inúmeras comparações e trocas que seriam realizadas, podendo ocasionar lentidão no procedimento que estiver sendo utilizado.