Shell Sort
Conceito
Shell sort é uma extensão do insertion
sort baseado em:
 Insertion
sort é bastante eficiente quando
a entrada está parcialmente classificada
 Insertion sort é ineficiente no caso geral
pois move os valores apenas uma posição
a cada vez
2
Descrição (1)
A proposta consiste em re-arrumar
objetos com intervalos maiores que
decrescerão até chegar ao intervalo 1
A etapa final é um verdadeiro Insertion
sort porém sobre um array de dados
quase completamente classificado
3
Descrição (2)
O processo consiste em
 Distribuir
a seqüência de dados a classificar
em um “array” bidimensional
 Classificar as colunas desse “array”
O processo se repete reduzindo número de
colunas do “array” até alcançar o valor 1
4
Descrição (3)
Os itens contidos em cada sub-lista não são
contíguos
Se houver 3 sub-listas cada sub-lista será
composta pelo i-ésimo elemento
No caso de 3 sub-listas



A primeira conterá os elementos das posições 1, 4, 7 e
assim por diante
A segunda conterá os elementos das posições 2, 5, 8 e
assim por diante
A terceira conterá os elementos das posições 3, 6, 9 e
assim por diante
5
Exemplo de shell sort (1)
Considere-se a seqüência de dados que se deseja
classificar
37905168420615734982
Inicia-se distribuindo a seqüência em um
determinado número de colunas
No exemplo serão consideradas 7 colunas
Cada coluna é classificada de cima para baixo em
ordem ascendente
A distribuição da esquerda é antes da classificação
e a da direita depois da classificação
6
Exemplo de shell sort (2)
3790516
3320515
8 4 2 0 6 1 5 -> 7 4 4 0 6 1 6
734982
879982
A seqüência assim obtida é redistribuída em
um número menor de colunas, 3 por
exemplo, e o processo repetido
7
Exemplo de shell sort (3)
332
051
574
4 0 6 ->
168
799
82
001
122
334
456
568
779
89
8
Exemplo de shell sort (4)
Basta agora distribuir em uma coluna e
repetir o processo uma última vez
Para caber em um slide a coluna será
exibida transposta
0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9
0 0 1 1 2 2 3 3 4 4 5 5 6 6 8 7 7 8 9 9
9
Exemplo de shell sort (5)
A seqüência de dados não é
distribuída em um “array”
bidimensional mas mantida em um
“array” unidimensional
adequadamente indexado
10
Número de “colunas”
Seja h o número de colunas a adotar
Para calcular a seqüência de valores de h pode-se adotar,
por exemplo
hM = 1, hM-1 = hM * 3 + 1
O resultado obtido é
..., 1093, 364, 121, 40, 13, 4, 1
Antes de iniciar a classificação é preciso determinar o
valor inicial de h (aproximadamente um terço do tamanho
do “array” a classsificar)
int h = 1; //valor inicial de h
while (h <= len / 3)
h = h * 3 + 1;
// (1, 4, 13, 40, 121, ...)
11
Programa com Shell Sort (1)
De://www.java2s.com/ExampleCode/Collections-Data-Structure/Shellsort.htm
public class ShellSort {
private long[] data;
private int len;
public ShellSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value){
data[len] = value;
len++;
}
public void display() {
System.out.print("Data:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
12
Programa com Shell Sort (2)
public void shellSort() {
int inner, outer;
long temp;
int h = 1; //valor inicial de h
while (h <= len / 3)
h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)
while (h > 0) // decrementar h, até que h=1
{ // classificar por colunas
for (outer = h; outer < len; outer++) {
temp = data[outer];
inner = outer;
// um sub-passo (por exemplo 0, 4, 8)
while (inner > h - 1 && data[inner - h] >= temp) {
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
h = (h - 1) / 3; // decrementar h
}
}
13
Programa com Shell Sort (3)
public static void main(String[] args) {
int maxSize = 10;
ShellSort arr = new ShellSort(maxSize);
for (int j = 0; j < maxSize; j++) {
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display();
arr.shellSort();
arr.display();
} // fim de main
} // fim de ShellSort
14