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); }
[editar] Código em PHP
function shellSort($arr_sort){ $pet=1; do{ $pet = 3*$pet+1; }while($pet <count($arr_sort)); do{ $pet /=3; for($i=$pet;$i<count($arr_sort);$i++) { $temp = $arr_sort[$i]; $j = $i - $pet; while($j >=0 && $temp < $arr_sort[$j]) { $arr_sort[$j + $pet] = $arr_sort[$j]; $j -= $pet; } $arr_sort[$j + $pet] = $temp; } }while($pet >1); return $arr_sort; }