Shell sort
Origem: Wikipédia, a enciclopédia livre.
Criado por Donald Shell em 1959, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.
Índice |
[editar] Implementações
[editar] Código em C++
template<class T>
void shell_sort( std::vector<T> &lista )
{
int h, size = static_cast<int>( lista.size() );
for( h = 1; h < size; h = 3 * h + 1 );
do
{
h /= 3;
for( int i = h; i < size; ++i )
{
T value = lista[i];
int j;
for( j = i - h; j >= 0 && value < lista[j]; j -= h )
{
lista[j+h] = lista[j];
}
lista[j+h] = value;
}
}
while( h > 1 );
}
[editar] Código em Java
private static void shellSort ( int [ ] v )
{
int i , j , h = 1, value ;
do { h = 3 * h + 1; } while ( h < v.length );
do {
h /= 3;
for ( i = h; i < v.length; i++) {
value = v [ i ];
j = i - h;
while (j >= 0 && value < v [ j ])
{
v [ j + h ] = v [ j ];
j -= h;
}
v [ j + h ] = value;
}
} while ( h > 1 );
}
[editar] Código em C
void shellSort( int * vet, int size ){
int i , j , value;
int gap = 1;
do {gap = 3*gap+1;} while ( gap < size );
do {
gap /= 3;
for ( i = gap; i < size; i++ ){
value =vet[i];
j = i - gap;
while ( j >= 0 && value < vet[j] ){
vet [j + gap] =vet[j];
j -= gap;
}
vet [j + gap] = value;
}
} while ( gap > 1);
}
