SHELLSORT ALGORITMOS DE ORDENAÇÕES
Por: Juliana2017 • 3/1/2018 • 942 Palavras (4 Páginas) • 315 Visualizações
...
Agora substituímos o v[mínimo] pelo v[i] formando com isto o novo vetor:
v[1]
v[2]
v[3]
v[4]
v[5]
v[6]
2
3
7
8
5
5
E assim vamos fazendo com os outros elementos até que todo o vetor esteja ordenado.65
Insertion Sort
Insertion sort é um algoritmo de ordenação simples, uma ordenação por comparações na qual uma nova lista é construída um valor por vez.
A complexidade do insertion sort no melhor caso é de (n) de acordo com Ziviani, visto que irá fazer n comparações e ver que o vetor já está ordenado. No pior caso e no caso médio a complexidade do insertion sort é de (n²).
Considera que o primeiro elemento está ordenado (ou seja, na posição correta). A partir do segundo elemento, insere os demais elementos na posição apropriada entre aqueles já ordenados.O elemento é inserido na posição adequada movendo-se todos os elementos maiores para posição seguinte do vetor.
EX:
O elemento da posição 0 (valor 60) é comparado com o elemento da posição 1 (valor 30).
0
1
2
3
4
60
30
40
20
10
Como o objetivo é ordenar crescentemente, os conteúdos dos elemetos da posições 0 e 1 devem ser trocados entre si.
0
1
2
3
4
30
60
40
20
10
Em seguida serão comparados os conteúdos dos elementos das posições 1 e 2:
0
1
2
3
4
30
60
40
20
10
Troca:
0
1
2
3
4
30
40
60
20
10
Elementos das posições 2 e 3:
0
1
2
3
4
30
40
60
20
10
Troca:
0
1
2
3
4
30
40
20
60
10
Elementos das posições 3 e 4:
0
1
2
3
4
30
40
20
60
10
Troca:
0
1
2
3
4
30
40
20
10
60
Apesar do vetor não estar ordenado ainda, observe que o maior elemento ficou na última posição:
0
1
2
3
4
30
40
20
10
60
O processo recomeça, porém ocorrerá entre as posições 0 e 3 (o elemento da posição 4 já está ordenado).
Elementos das posições 0 e 1.:
...