SHELLSORT ALGORITMOS DE ORDENAÇÕES

Faculdade Fortium

Sistema da Informação

ALGORITMOS DE ORDENAÇÕES

Selection, Insertion e Bubble Sort.

Leidiane dos Santos Barbosa

Brasília

11 de novembro de 2015

---

INTRODUÇÃO

O algoritmo é um processo de resolução de uma determinada tarefa para a qual ele foi designado. Falaremos especificamente sobre o algoritmo de ordenação. Em programação, um algoritmo de ordenação tem com objetivo realizar a ordenação de uma lista de valores. Citaremos três deles, 1º Isertion Sort que é ordenação por inserção, 2º Selection Sort ordenação por seleção é o 3º Bubble Sort Ordenação por troca. O Selection Sort é um método de ordenação por seleção. Ele percorre a lista em busca do menor valor e o move para a posição correta precedido sempre do elemento de menor valor. O Insertion Sort ou Ordenação por inserção é um método simples de ordenação que percorre um vetor ordenando os elementos a esquerda a medida que avança. É para finalizar temos o Bubble Sort é um algoritmo de ordenação mais simples que tem como característica percorrer a vista várias vezes e a cada passagem fazendo flutuar para o topo o maior elemento da sequência.

---

---

.

---

 

Selection Sort

É um método simples de ordenação, baseada em se passar sempre o menor valor do vetor para a primeira posição ou o maior dependendo da ordem requerida, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n - 1) elementos restantes, até os últimos elementos.

Princípio de funcionamento:

1. Seleciona o menor item do vetor (ou o maior).
2. Troque-o com o item que está na primeira posição

Repita estas duas operações com os n-1 itens restantes, depois com os n-2 intens, até que reste apenas um elemento.

A ordenação por seleção consiste, em cada etapa, em selecionar o maior ou menor, elemento e colocá-lo em sua posição correta dentro da futura lista ordenada.

Durante a aplicação do método de seleção a lista com n registros fica decomposta em duas sub listas, uma contendo os itens já ordenados e a outra com os restantes ainda não ordenados.

• No início a sub lista ordenada é vazia e a outra contém todos os demais.
• No final do processo a sub lista ordenada apresentará (n-1) itens e a outra apenas 1.  

As etapas, consistem em buscar o maior (ou menor) elemento da lista não ordenada e colocá-lo na lista ordenada. Visando demonstrar o resultado das etapas da ordenação de um vetor de inteiros, consideraremos o ordenamento crescente dos elementos e selecionaremos em cada etapa o maior elemento do subvetor não ordenado.

EXEMPLO DE FUNCIONAMENTO (TIAGO MADEIRA)

O programa recebe o seguinte vetor.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

Começa com i = 1.

v[1]	v[2]	v[3]	v[4]	v[5]	v[6]
5	3	7	8	2	5

Ele marca o próprio índice i como a variável mínimo, que é sempre o menor elemento do vetor. Então, ele faz um para de i = 2 até o comprimento do vetor, com o objetivo de descobrir qual o menor elemento.

i = 2...  ... v[j] = 7 > v[mínimo] = v [2] = 3, portanto não mexemos em nada.

i = 4...  ... v[j] = 8 > v[mínimo] = v [2] = 3, portanto não mexemos em nada.

j = 5...  ...v[j] = 5 > v[mínimo] = v [5] = 2, portanto não mexemos em nada.

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. 

...