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.

[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);
      }