gnome

GNOME SHORT
Conceito
Algoritmo similiar ao InsertionSort com a diferença que o GnomeSort leva um elemento para sua posição correta, com uma sequencia grande de trocas assim como o BubbleSort.
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.
Exemplo:
12 9 7 6 4
9 7 6 4 6
7 6 4 7 7
6 4 9 9 9
4 12 12 12 12

O numero 12 é maior e está antes do numero 9, então foi feita a troca de posições dos elementos e o algoritmo volta com o 12 fazendo a comparação dos elementos dois a dois e inserindo o no lugar certo, como mostra a figura.
Após iniciamos a comparação do 7 com o 6, trocamos as posições e o algoritmo volta com o 7 até inseri-lo na posição correta, desta maneira todos os elementos serão ordenados corretamente, como mostra a ultima tabela.

Shell Sort
Conceito
Shell sort é uma extensão do insertion sort baseado em:
Insertion sort é bastante eficiente quando a entrada está parcialmente classificada
Insertion sort é ineficiente no caso geral, pois move os valores apenas uma posição a cada vez.
A proposta consiste em re-arrumar objetos com intervalos maiores que decrescerão até chegar ao intervalo 1.
A etapa final é um verdadeiro Insertion sort, porém sobre um array de dados quase completamente classificado.
O processo consiste em:
Distribuir a sequencia de dados a classificar em um “array” bidimensional
Classificar as colunas desse “array”
O processo se repete reduzindo número de colunas do “array” até alcançar o valor 1.
Os itens contidos em cada sub-lista não são contíguos.
Se houver 3 sub-listas cada sub-lista será composta pelo milésimo elemento.
No caso de 3 sub-listas:
A primeira conterá os elementos das