Gnome sort
Origem: Wikipédia, a enciclopédia livre.
Algoritmo similiar 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
Características
Complexidade de tempo: Θ(n2)
Índice |
[editar] Implementações
[editar] Código em C++ versão 1
template<class T>
void gnome_sort( std::vector<T> &lista )
{
std::vector<T>::size_type i = 1;
while( i < lista.size() )
{
if( i == 0 || lista.at( i-1 ) <= lista.at( i ) )
{
i++;
}
else
{
std::swap( lista[ i - 1 ], lista [ i ] );
--i;
}
}
}
[editar] Código em C++ versão 2
template<class T>
void gnome_sort( std::vector<T> &lista )
{
std::vector<T>::iterator elem = lista.begin()+1;
while( elem != lista.end() )
{
if( elem == lista.begin() || *(elem-1) <= *elem )
{
++elem;
}
else
{
std::iter_swap( elem-1, elem );
--elem;
}
}
}
[editar] Código em Java
public class gnome
{
public static void gnomeSort(int[] v)
{
int i = 1, troca = 0;
while(i < v.length)
{
if (i == 0 || v [i-1] <= v [i])
i++;
else
{
troca = v [i - 1];
v[i - 1] = v[i];
v[i] = troca;
i --;
}
}
}
public static void main (String [] aaa)
{
gnomeSort(int[]);
}
}
