Shell sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Shell sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso depende da sequência do gap. Melhor conhecida: O(n\log^2 n)
complexidade caso médio depende da sequência do gap
complexidade melhor caso O(n)
complexidade de espaços pior caso O(n)
Algoritmos
Shell sort bares algoritmo de cores

Criado por Donald Shell em 1959,[1] publicado pela Universidade de Cincinnati, Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.[2] O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles.[3] 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. Implementações do algoritmo. Procure a versão em inglês desse mesmo link.

Código em Java[editar | editar código-fonte]

public static void shellSort(Integer[] nums) {
    int h = 1;
    int n = nums.length;
    while(h < n)
            h = h * 3 + 1;
    h = h / 3;
    int c, j;
    while (h > 0) {
        for (int i = h; i < n; i++) {
            c = nums[i];
            j = i;
            while (j >= h && nums[j - h] > c) {
                nums[j] = nums[j - h];
                j = j - h;
            }
            nums[j] = c;
        }
        h = h / 2;
    }
}

Código em Python[editar | editar código-fonte]

    while h > 0:
        for i in range(h, n):
            c = nums[i]
            j = i
            while j >= h and c < nums[j - h]:
                nums[j] = nums[j - h]
                j = j - h
                nums[j] = c
        h = int(h / 2.2)

Código em C++[editar | editar código-fonte]

void ShellSort( apvector <int> &num) {
     int i, temp, flag = 1, numLength = num.length( );
     int d = numLength;
     while( flag || (d > 1)) {                    // boolean flag (true when not equal to 0)
          flag = 0;                               // reset flag to 0 to check for future swaps
          d = (d+1) / 2;
          for (i = 0; i < (numLength - d); i++) {
               if (num[i + d] > num[i]) {
                      temp = num[i + d];         // swap positions i+d and i
                      num[i + d] = num[i];
                      num[i] = temp;
                      flag = 1;                  // tells swap has occurred
               }
          }
     }
     return;
}

Código em C[editar | editar código-fonte]

void shellSort(int *vet, int size) {
    int i , j , value;
    int gap = 1;
    while(gap < size) {
        gap = 3*gap+1;
    }
    while ( gap > 1) {
        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;
        }
    }
}

Código em PHP[editar | editar código-fonte]

function shellSort($arr_sort){
   $pet = 1;
   do {
      $pet = 3 * $pet + 1;
   } while ($pet < count($arr_sort));
   do {
      $pet /= 3;
      $pet = intval($pet);
      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;
}

Código em Ruby[editar | editar código-fonte]

def shellSort( array )
    n = array.length
    h = n/2
    while h > 0
        for i in (h...n)
     c = array[i]
     j = i
     while j  >= h and c < array[j-h]
         array[j] = array[j-h]
         j = j-h
         array[j] = c
     end
        end
        h = (h/2.2).to_i
    end
end

Exemplo de execução[editar | editar código-fonte]

Execução:

Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9

1, 43, 12, 6, 56, 23, 52, 9

1, 6, 12, 23, 56, 43, 52, 9

1, 6, 12, 23, 52, 43, 56, 9

1, 6, 12, 23, 52, 9, 56, 43

1, 6, 12, 9, 52, 23, 56, 43

1, 6, 9, 12, 52, 23, 56, 43

1, 6, 9, 12, 23, 52, 56, 43

1, 6, 9, 12, 23, 52, 43, 56

1, 6, 9, 12, 23, 43, 52, 56

Em negrito estão os números trocados na atual iteração.

Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.

Conclusão[editar | editar código-fonte]

A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na sequência obtida. Por ser um método de complexidade O(n^2 ) não é aconselhável a sua implementação para sequências grandes, mas possui uma boa eficiência para as pequenas e medianas.

Referências

  1. AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996. ISBN 85-352-0004-5
  2. WIRTH, Niklaus. Algoritmos e Estruturas de Dados. Rio de Janeiro: Prentice-Hall do Brasil, 1989. 61-63 p. ISBN 85-7054-033-7
  3. Veloso, Paulo; SANTOS, Clesio dos; AZEREDO, Paulo; FURTADO, Antonio. Estruturas de Dados. 4ª ed. Rio de Janeiro: Campus, 1986. 184-185 p. ISBN 85-7001-352-3

Ver também[editar | editar código-fonte]