10 Algoritmos de Ordenação

Prévia do material em texto

Relembrando 
Algoritmos de 
Ordenação 
Edian F. Franco De Los Santos
Prof.edianfranco@gmail.com
Selection Sort 
Métodos simples
Selection Sort 
Algoritmo de ordenação por seleção 
A ordenação por seleção ou selection sort consiste 
em selecionar o menor item e colocar na primeira 
posição, selecionar o segundo menor item e colocar 
na segunda posição, segue estes passos até que 
reste um único elemento. Para todos os casos 
(melhor, médio e pior caso) possui complexidade 
C(n) = O(n²) e não é um algoritmo estável
Funcionamento 
• Neste algoritmo de ordenação sera eleito o segundo numero 
do vetor para iniciar as comparações.
• Os elementos à esquerda do numero eleito estão sempre 
ordenados de forma crecente ou descrescente. 
• Um laço com as comparações sera executado do segundo 
elemento ao ultimo, ou seje, na quantidade de vezes igual ao 
numero de elemento do vetor menos um (for (i=1; i<n;i+
+)). 
• Enquanto exixterem elementos à esquerda do numero eleito 
para comparações e a posição que atende a ordenação que 
se busca não for encontrada, o laço será executado. 
Funcionamento 
• O numero eleito está na posição i. 
• Os números à esquerda do eleito estão na posição i-1 
à 0, 
• logo o laço a ser executado será (j=i-1) e (while (j>=0 
&& elemento [j] > eleito)). 
BUBBLE SORT
Métodos Simples 
BUBBLE SORT
Algoritmo de ordenação por troca
• Neste algoritmo de ordenação serão efetuadas 
comparações entre os dados armazenados em um 
vetor de tamanho N.
• Cada elemento de posição i será comparado como 
o elemento na posição i+1, e quando a ordenação 
procurada (crescente ou decrescente) é 
encontrada , uma troca de posições entre os 
elemento é feita. 
• Um laço com a quantidade de elementos do vetor 
será executado (for (j=1; j<=n; j++)), e dentro 
deste um laço que percorre da primeira à 
penúltima posição do vetor (for(i=0<n-1; i++) 
Algoritmo
JAVA
Métodos efcientes 
Métodos Efcientes 
Os métodos efcientes são mais complexos nos 
detalhes, requerem um número menor de 
comparações. São projetados para trabalhar com 
uma quantidade maior de dados e possuem 
complexidade C(n) = O(n log n). Exemplos: Quick 
sort, Merge sort, Shell sort, Heap sort, Radix sort, 
Gnome sort, Count sort, Bucket sort, Cocktail sort, 
Timsort.
MERGE SORT
Métodos Efcientes 
MERGE SORT
Algoritmo de ordenação por 
intercalação 
• Criado em 1945 pelo matemático americano John 
Von Neumann o Mergesort é um exemplo de 
algoritmo de ordenação que faz uso da estratégia 
“dividir para conquistar” para resolver problemas.
• É um método estável e possui complexidade C(n) 
= O(n log n) para todos os casos.
• Esse algoritmo divide o problema em pedaços 
menores, resolve cada pedaço e depois junta 
(merge) os resultados.
Funcionamento 
• Neste algoritmo de ordenação, o vetor é dividido 
em vetores com a metade do tamanho original por 
médio de um procedimento recursivo. 
• Recursividade: propriedade daquilo que se pode 
repetir um número indefnido de vezes.
• Essa divisão ocorre ate que o vetor fque com 
apena um elemento e este seja ordenado e 
intercalados. 
Divisão e conquista 
• Neste algoritmo, é aplicada a técnica da divisão e 
conquista, uma técnica recursiva que envolve três 
passos em cada nível da recursão:
1. Dividir o problema em um certo numero de 
subproblemas.
2. Conquistar os subproblemas solucionando-os 
recursivamente. Se os tamanhos dos subproblemas são 
sufcientemente pequenos, então, solucionar os 
subproblemas de forma simples.
3. Combinar as soluções dos subproblemas na solução de 
problema original. 
Divisão e conquista no MERGE 
SORT
• No algoritmo de ordenação por intercalação, MERGE 
SORT, tem-se a técnica da divisão e conquista da 
seguinte forma: 
1. Dividir: dividir a sequencia de n elementos a serem 
ordenados em duas subsequências de n/2 elementos 
cada.
2. Conquistar: ordenar as duas sequencia recurvisavemte 
utilizando a ordenação por intercalação. 
3. Combonar> intercalar as duas subsequências 
ordenadas para produzir a solução. 
Algoritmo
JAVA
Relembrando 
Algoritmos de Ordenação
e
Algoritmos de busca 
Edian F. Franco De Los Santos
Prof.edianfranco@gmail.com
Shell Sort
Métodos efcientes 
Shell Sort
Ordenação por Inserção
• Criado por Donald Shell em 1959, o método Shell 
Sort é uma extensão do algoritmo de ordenação 
por inserção. 
• Ele permite a troca de registros distantes um do 
outro, diferente do algoritmo de ordenação por 
inserção que possui a troca de itens adjacentes 
para determinar o ponto de inserção. 
• A complexidade do algoritmo é desconhecida, 
ninguém ainda foi capaz de encontrar uma 
fórmula fechada para sua função de complexidade 
e o método não é estável.
Funcionamento 
• Os itens separados de h posições (itens distantes) 
são ordenados: o elemento na posição x é 
comparado e trocado (caso satisfaça a condição de 
ordenação) com o elemento na posição x-h. Este 
processo repete até h=1, quando esta condição é 
satisfeita o algoritmo é equivalente ao método de 
inserção.
• A escolha do salto h pode ser qualquer sequência 
terminando com h=1. 
Shell Sort
• Os itens separados de h posições são 
rearranjados.
• Todo h-ésimo item leva a uma sequência 
ordenada.
• 
• Tal sequência é dita estar h-ordenada
Quick Sort
Métodos efcientes 
Algoritmo de ordenação rápida
Quick Sort 
• Neste algoritmo o vector e particionado em dos 
por meio de uma procedimento recursivo. 
• Essa divisão ocorre até que o vetor fque com 
apenas um elemento, enquanto os demais fcam 
ordenados à medida que ocorre o 
particionamento. 
• Esse algoritmo também é baseado na técnica da 
divisão e conquista. 
Funcionamento 
• Dividir: o vetor X[p..r] é particionado 
(rearranjando) em dois subvetores não vazios 
X[p..q] e X[q+1..r], tais que cada elemento de 
X[p..q] e menor ou igual a cada elemento de 
X[p..r]. O índice q é calculado como parte do 
processo de particionamento. 
• Para determinar o índice q, escolhe-se o elemento 
que encontra na metade do vetor original, 
chamado pivô, e rearranjam-se os elementos do 
vetor de forma que os que fcarem à esquerda de 
q são menores (ou iguais ) ao pivô e os fcarem na 
direita de q são maiores (ou iguais) ao pivô 
Funcionamento 
• Conquistar : os dosi vetores são ordenados 
X[p..q] e X[q+1..r] por chamada recursiva ao 
Quick sort.
• Combinar: Durante o processo recursivo os 
elementos vão sendo ordenados no próprio vetor 
não exigindo nenhum processamento nesta etapa. 
Algoritmos de Busca
Algoritmos de Busca 
Algoritmos de Busca 
Os algoritmos de busca têm como base o método de 
procura de qualquer elemento dentro de um 
conjunto de elementos com determinadas 
propriedades.
 Que podiam ser livros nas bibliotecas, ou dados 
cifrados, usados principalmente durante as duas 
grandes guerras
Tipos de algoritmos 
Os algoritmos podem ser classifcados em dois 
tipos:
• Busca Sequencial: São analisados os elementos 
de uma coleção de um em um até encontrar o 
valor desejado.
• Busca Binaria: Baseada na ideia de que a 
coleção de dados em que será feita a busca esta 
ordenada. 
Algoritmos de Busca
Sequencial 
Algoritmo de busca sequencial
• Pode ser executado em um vetor não ordenado e 
em um vetor ordenado.
• Em um vetor não ordenado, será buscado o 
numero até que ele seja encontrado ou ate chegar 
ao fnal do vetor. 
• Em um vetor ordenado, será buscado o numero 
até que ele seja encontrado e enquantofor maior 
que o numero do vetor. 
Algoritmo de busca sequencial
Neste tipo de algoritmo, o melhor processamento 
que podemos esperar é que o valor encontrado 
esteja na primeira posição, mas caso tenhamos 
uma coleção de dados muito grande , se o valor esta 
na ultima posição, teremos um custo muito grande 
de processamento, sendo necessário n 
processamentos.
Não 
Ordenado
Ordenado 
Algoritmos de Busca
Binaria 
Algoritmo de busca binaria
• O algoritmo de busca binaria é executado somente em vetores 
ordenados.
• Nesse algoritmo o vetor com os dados é dividido ao médio e o 
numero do meio é comparado com o numero procurado.
• Se este forem iguais, a busca termina, caso contrario, se o 
numero procurado é menor que o do meio a busca será 
realizada no vetor à esquerda ao do meio.
• Se o numero procurado é maior que o do meio, a busca será 
realizada no vetor à direita ao vetor do meio.
• Esse procedimento de divisão e comparação acontece até que o 
vetor de dados fque com apenas um elemento ou ate o numero 
procurado ser encontrado
Exercícios