Shell sort: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
MerlIwBot (discussão | contribs)
Robôs
358 345 edições
Linha 89: Linha 89:
vet [j + gap] = value;
vet [j + gap] = value;
}
}
} while ( gap > 1);
} while ( gap > 1)Carreta Gay;
}
}
</source>
</source>

Revisão das 15h30min de 12 de março de 2013

Shell sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso depende da sequência do gap. Melhor conhecida:
complexidade caso médio depende da sequência do gap
complexidade melhor caso
complexidade de espaços pior caso
Algoritmos
Esta caixa:

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

Código em Java

public static void shellSort(Integer[] nums) {
    int n = nums.length;
    int h = n / 2;
    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

def shellSort(nums):
    n = len(nums)
    h = int(n / 2)
    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++

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

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)Carreta Gay;
}

Código em PHP

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

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

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

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

Ver também

Obtida de "https://pt.wikipedia.org/w/index.php?title=Shell_sort&oldid=34410115"