Radix sort

Origem: Wikipédia, a enciclopédia livre.

O Radix sort é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia.

Características

Complexidade de Tempo: Θ(nk).
Complexidade de espaço: Θ(n + s).
– n = número de elementos.
– k = tamanho string.
– s = tamanho do alfabeto.

[editar] Implementações

[editar] Código em Java

      private static final int MAX_CHARS = 28;
       private static void radixSort (String [] v) 
      { 
         Queue queues [ ] = createQueues();
         for ( int pos = maxSize( v ) - 1; pos >= 0; pos--) 
         { 
            for (int i = 0; i < v.length; i++) 
            { 
               int q = queueNo( v [ i ], pos );
               queues [ q ].enqueue( v [ i ] );
            }
            restore ( queues, v );
         }
      }
       private static void restore ( Queue [ ] qs, String [ ] v) 
      { 
         int contv = 0;
         for ( int q = 0; q < qs.length; q++ )
            while (! qs[ q ].empty( ) )
               v [ contv++ ] = qs [ q ].dequeue( );
      }
        
       private static int [] copia(int [] v, int inf , int sup)
      {
         int vcopy[] = new int[sup - inf + 1];
         for (int i = 0; i < vcopy.length; i++)
            vcopy[ i ] = v[ inf + i ];
         return vcopy;
      }
       private static Queue[] createQueues()
      { 
         Queue[] result = new Queue [ MAX_CHARS ];
         for (int i = 0; i < MAX_CHARS; i++)
            result [ i ] = new Queue();
         return result ;
      }
   
       private static int queueNo ( String string , int pos) 
      { 
         if (pos >= string.length ()) 
            return 0;
         char ch = string .charAt(pos);
         if (ch >= ’A’ && ch <= ’Z’) 
            return ch - ’A’ + 1;
         else if (ch >= ’a’ && ch <= ’z’) 
            return ch - ’a’ + 1;
         else 
            return 27;
      }
       private static int maxSize(String [] v)
      {
         int maiorValor = v[0]. length ();
      
         for (int i = 1; i < v.length; i++)
            if (maiorValor < v[i ]. length ())
               maiorValor = v[i ]. length ();
         return maiorValor;
      }