Shell sort
| Shell sort | |
|---|---|
| classe | Algoritmo de ordenação |
| estrutura de dados | Array, Listas ligadas |
| complexidade pior caso | depende da sequência do gap. Melhor conhecida: [carece de fontes] |
| complexidade caso médio | depende da sequência do gap |
| complexidade melhor caso | [carece de fontes] |
| complexidade de espaços pior caso | |
| 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. Veja 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]
def shellSort(nums): h = 1 n = len(nums) 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) return nums Código em C++11[editar | editar código-fonte]
template <typename T> void shell_sort(std::vector<T> &v) { int h = 1; int i, j; int rep = 0; while (h < v.size()) { h = h*3+1; } while (h > 1) { h /= 3; for (i = h; i < v.size(); i++) { T aux = v[i]; j = i; while (j >= h && aux < v[j-h]) { v[j] = v[j-h]; j -= h; rep++; } v[j] = aux; } } } Código em C[editar | editar código-fonte]
void shellSort(int *vet, int size) { int i, j, value; int h = 1; while(h < size) { h = 3*h+1; } while (h > 0) { for(i = h; i < size; i++) { value = vet[i]; j = i; while (j > h-1 && value <= vet[j - h]) { vet[j] = vet[j - h]; j = j - h; } vet[j] = value; } h = h/3; } } 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 && 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 Código em Swift[editar | editar código-fonte]
func shellSort<T:Comparable>(_ input:[T]) -> [T] { var items : [T] = input let itemsCount : Int = items.count var gapSize : Int = items.count let minGapSize : Int = 1 let half : Int = 2 var swaped : Bool = true while !swaped || gapSize > minGapSize { swaped = false gapSize = (gapSize + 1) / half for (index, _) in items.enumerated() where index < (itemsCount - gapSize) { let indexToCompare = index + gapSize if items[index] > items[indexToCompare] { swap(&items[index], &items[indexToCompare]) swaped = true } } } return items } Código em JavaScript[editar | editar código-fonte]
public void shellSort(int[] array) { int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 }; int temp; int i, j; for (int gap : gaps) { for (i = gap; i < array.length; i++) { temp = array[ i ]; for (j = i; j >= gap && array[ j - gap ] > temp; j -= gap) { array[ j ] = array[ j - gap ]; } array[ j ] = temp; } } } 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, 43, 56, 23, 52, 9
1, 6, 12, 43, 52, 23, 56, 9
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. Devido a sua complexidade possui excelentes desempenhos em N muito grandes, inclusive sendo melhor que o Merge Sort.
Referências
- ↑ 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
- ↑ WIRTH, Niklaus (1989). Algoritmos e Estruturas de Dados. Rio de Janeiro: Prentice-Hall do Brasil. pp. 61–63. ISBN 85-7054-033-7
- ↑ 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
