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.
- ↑ 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