Shell Sort

5/9/2018 Shell Sort - slidepdf.com

http://slidepdf.com/reader/full/shell-sort-559bf5adc32a7 1/11

O algoritmo Shellsort

Inventado por Donald Shell em 1959 (daí o nome Shell);

Também conhecido como ordenação por diminuição de

incrementos;

Princípio básico: O algoritmo Shellsort ordena uma seqüencia

a1, a2, . . . , an de n elementos pela ordenação de sucessivassubseqüencias cujos valores estão misturados na seqüencia

original.

As subseqüencias a serem ordenadas são determinadas pela

seqüencia de parâmetros ht, ht−1, . . . , h1 denominados

incrementos. Destes, é obrigatório que sempre h1 = 1.

1. Começando por ht, divide-se a seqüencia original em ht

subseqüencias contendo aproximadamente n/ht elementos.




Princípio básico (cont.):

Os elementos que iniciam cada subseqüencia são os ht primeiroselementos da seqüencia original e dentro de cada subseqüencia

os elementos distam de ht posições entre si;

2. Estas primeiras subseqüencias são ordenadas utilizando-se

qualquer outro algoritmo de ordenação;

3. Repetem-se os passos 1 e 2 para ht−1, ht−2, . . . , h1, quando

então a seqüencia ficará ordenada.




Observações

1. Para ordenar as subseqüencias utiliza-senormalmente o algoritmo de inserção;

2. Testes empíricos sugerem que a melhor escolha

para os valores deh

é a seqüencia3t−1

2, . . . , 13, 4, 1, onde ht = 3ht−1 + 1;

3. t representa o número de subseqüencias aconsiderar, que pode ser expresso em função de n

(número de elementos) como t = log3(2n + 1).




Exemplo de aplicação

Considere o exemplo abaixo com hk = 6, 4, 3, 2, 1, para k = 5, . . . , 1. Primeiro,

separamos a seqüencia em 6 subseqüencias de tamanho 2 cada:

7 19 24 13 31 8 82Seqüencia

Original

(h5=6)

18 44 63 5 29

1asublista

(7,82)

2asublista(19,18)

3asublista(24,44)

4asublista(13,63)

5asublista

(31,5)

6asublista

(8,29)




Exemplo de aplicação (cont.)

Agora, com as subseqüencias ordenadas do passo anterior, separamos a seqüencia em

4 subseqüencias de tamanho 3 cada:

7 18 24 13 5 8 82(h4=4) 19 44 63 31 29

1asublista

(7,5,44)

2a

sublista

(18,8,63)

3a

sublista

(24,82,

31 )

4a

sublista

(13,19,

29 )





Das subseqüencias ordenadas do passo anterior, separamos a seqüencia em 3

subseqüencias de tamanho 4 cada:

5 8 24 13 7 18 31(h3=3) 19 44 63 82 29

1a

sublista

(5,13,31,63 )

2a

sublista(8,7,19,

82 )

3a

sublista

(24,18,

44,29)






subseqüencias de tamanho 6 cada:

5 7 18 13 8 24 31(h2=2) 19 29 63 82 44

1a

sublista

(5,18,8,31,29,

82 )

2a

sublista

(7,13,24,

19,63,

44 )






seqüencia de tamanho 12:

5 7 8 13 18 19 29(h1=1) 24 31 44 82 63

1a

sublista(5,7,8,

13,18,

19,29,

24,31,

44,82,

63 )





A ordenação da seqüencia anterior leva a resposta do problema:

5 7 8 13 18 19 24 29 31 44 63 82

Seqüencia ordenada




Algoritmo

1 procedimento Shellsort(A,n)2 inicio

3 t←CalcularNumIncrementos(n) {tamanho da seq. h}

4 InicializarIncrementos (h, t ) {det . os valores dos h’s →vetor}

5 para s←t ate 1 faca

6 inicio

7 para i←h[s]+1 ate n faca

8 { inicio a ordenacao da subseq.}9 x←A[i]

10 j←i−h[s]




Algoritmo (cont.)

11 enquanto (j>0) e (A[j]>x) faca12 A[j+h[s]]←A[j]

13 j← j−h[s]

14 fim enquanto

15 A[j+h[s]]←x

16 fim para

17 fim para

18 fim

Documents

Shell Sort