Método ShellSort: Conceito e Implementação

Prévia do material em texto

Método de Método de 
Ordenação ShellSortOrdenação ShellSort
IFG – Instituto Federal de Goiás Campos Luziânia
Estrutura de Dados II
Alunos: Wilson e Breno
 
Introdução ao Método ShellSortIntrodução ao Método ShellSort
➔ Criado por Ronald L. Shell, em 1959.
➔ E um métodos de ordenação interna.
➔ É uma extensão do algoritmo de ordenação por inserção.
➔ O método de Shell contorna este problema permitindo 
trocas de registros distantes um do outro.
➔ Shell sort é o mais eficiente algoritmo de classificação 
dentre os de complexidade quadrática
 
Implementação do shellSortImplementação do shellSort
➔O diferencial do ShellSort é a divisão em h intervalos que ele 
realiza para posteriomente aplicar o método de inserção.
➔ Os itens separados de h posições são rearranjados.
➔Todo h-ésimo item leva a uma sequência ordenada.
➔Tal seqüência é dita estar h-ordenada.
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
3 0 1 8 7 2 5 4 9 6
0 1 2 3 4 5 6 7 8 9
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
3 0 1 8 7 2 5 4 9 6
0 1 2 3 4 5 6 7 8 9
c = 2 hij
3 2
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
2 0 1 8 7 3 5 4 9 6
0 1 2 3 4 5 6 7 8 9
c = 5 h i,j
0 5
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
2 0 1 8 7 3 5 4 9 6
0 1 2 3 4 5 6 7 8 9
c = 4 h i,j
1 4
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
2 0 1 8 7 3 5 4 9 6
0 1 2 3 4 5 6 7 8 9
c = 9 h i,j
8 9
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
2 0 1 8 7 3 5 4 9 6
0 1 2 3 4 5 6 7 8 9
C = 6 h i,j
7 6
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
2 0 1 8 6 3 5 4 9 7
0 1 2 3 4 5 6 7 8 9
hij c = 1
2 1
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 8 6 3 5 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 8
0 8
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 8 6 3 5 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 6
2 6
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 8 6 3 5 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 3
8 3
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 6 8 5 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 3
0 3
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 6 8 5 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 5
6 5
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 8 6 4 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 5
2 5
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 8 6 4 9 7
0 1 2 3 4 5 6 7 8 9
h c = 4 i,j
8 4
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 4 6 8 9 7
0 1 2 3 4 5 6 7 8 9
h i,j c = 4
3 4
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 4 6 8 9 7
0 1 2 3 4 5 6 7 8 9
h c = 9 i,j
6 9
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 4 6 8 9 7
0 1 2 3 4 5 6 7 8 9
h c = 7 j i,j
8 7
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h c = 7 i,j
4 7
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
1 0 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
hij c = 0
1 0
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h i,j c = 2
1 2
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h i,j c = 3
2 3
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h i,j c = 5
3 5
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h i,j c = 4
5 4
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h i,j c = 6
5 6
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h c = 7 i,j
6 7
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h c = 9 i,j
7 9
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 5 4 6 7 9 8
0 1 2 3 4 5 6 7 8 9
h c = 8 i,j
9 8
 
Implementação do shellSortImplementação do shellSort
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;
 } 
 }
●
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
 
ConclusãoConclusão
➔ A ordenação Shell utiliza a quebra sucessiva da sequência.
➔ Por ser um método de complexidade O(n² ) não é 
aconselhável a sua implementação para sequências grandes, 
mas possui uma boa eficiência para as pequenas e medianas.
 
Estudo da ComplexidadeEstudo da Complexidade
➔O estudo da complexidade deste algoritmo contém alguns 
problemas matemáticos muito difíceis, a começar pela própria 
sequencia de incrementos para h. 
➔De acordo com testes empíricos utilizando a formula abaixo 
para o calculo dos incrementos, a ordem de complexidade do 
ShellSort é de aproximadamente O(nⁱ; 25) ou O(n(log n)²) [?].
h(s > 1) = 3h(s -1) + 1
h(s = 1) = 1
ShellSortShellSort
➔ Vantagens:
➔ Shellsort é uma ótima opção para arquivos de tamanho 
moderado.
➔ Sua implementação é simples e requer uma quantidade 
de código pequena.
➔ Desvantagens:
➔ O tempo de execução do algoritmo é sensível à ordem 
inicial do arquivo.
➔ O método não é estável,
Referências Bibliográ�casReferências Bibliográ�cas
➔ Nivio Ziviani. Projeto de Algoritmos com implementação 
em C++ e Java. THOMSON Learning, São Paulo, 1st 
edition, 2007
➔ Michael Lamont. Shell sort, 2008.http://linux.wku.edu/~
lamonml/algor/sort/shell.html.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35