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

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 pp. 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 pp. ISBN 85-7001-352-3.

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