Embed Size (px)
Citation preview
Por que ordenar os dados?
“Encontrar elementos em uma lista torna-se algo simples e
fica facilitado quando esses dados estão ordenados; algo como
procurar um nome em uma lista em ordem alfabética.”
(PUGA; RISSETTI, 2009, p.133).
“A aplicação de técnicas específicas para a classificação de
dados garante os mecanismos de manutenção da ordem dos
arquivos e a melhora no desempenho das aplicações.”
(OLIVEIRA; TAVEIRA; BOTINI, 1999, p.50).
Como ordenar os dados?
Existem diversas técnicas, entre elas:
Ordenação por trocas (bubble sort);
Ordenação por seleção (selection sort);
Ordenação por inserção (insertion sort);
Ordenação por intercalação (merge sort);
Ordenação quick sort;
Ordenação heap sort;
Ordenação por trocas
Talvez a estratégia mais simples para ordenar um vetor
seja comparar pares de itens consecutivos e permutá-los,
caso estejam fora de ordem.
Em cada fase desse método, um item de maior valor é
deslocado para sua posição definitiva no vetor ordenado.
Ordenação por trocas
Ordenação completa de um vetor pelo método da bolha
Ordenação por trocas
Então, se um vetor tem n itens, após a primeira fase
haverá n - 1 itens a ordenar. Usando a mesma estratégia,
após a segunda fase, teremos n - 2 itens, depois n - 3 e
assim sucessivamente até que reste um único item.
É possível constatar que para ordenar n itens bastam
apenas n - 1 fases e que, numa determinada fase i, são
realizadas n - i comparações.
Ordenação por trocas
Análisando a ordenação por trocas (bubble sort),
verifica-se que o número total de comparações realizadas
é:
(n - 1)+(n - 2)+(n - 3)+…+2+1 = ½(n2 - n)
Como a cada comparação corresponde uma troca em
potencial, no pior caso serão realizadas no máximo
½(n2- n) trocas
Sua complexidade é, portanto, O(n2)
Ordenação por troca
Resumindo ...
Efetua sucessivas comparações de elementos dois a dois,
com a conseqüente troca desses elementos;
Bublle sort
Mais conhecida dentre as técnicas
Fácil de compreender e de implementar;
Baixo desempenho em comparação às outras.
Ordenação por seleção
O passo básico do selection sort consiste em selecionar
o maior valor do vetor e permutá-lo com o último;
Repete-se o processo, supondo que o vetor tem um item
a menos;
Passo Pos. atual Pos.
selecionada V[1] V[2] V[3] V[4] V[5]
1º 5 2 38 50 46 19 27
2º 4 3 38 27 46 19 50
3º 3 1 38 27 19 46 50
4º 2 2 19 27 38 46 50
- - - 19 27 38 46 50
Ordenação por seleção Análisando a ordenação por trocas (selection sort),
verifica-se que o número total de comparações realizadas é:
(n - 1)+(n - 2)+(n - 3)+…+2+1 = ½(n2 - n)
Sua complexidade é, portanto, O(n2)
A vantagem é que o número de trocas é sempre O(n), visto que o procedimento de troca é chamado n - 1 vezes.
Ordenação por seleção
Resumindo...
Selection sort
Simples e de fácil entendimento;
Baixo desempenho para ordenar grandes quantidades
de informações.
Ordenação por inserção
Supõe que um prefixo do vetor jé está ordenado e que o
resto está desordenado;
Em cada fase, o primeiro item do resto do vetor é
removido e inserido em sua posição correta dentro do
prefixo ordenado;
À medida que a ordenação avança, o prefixo aumenta e o
resto diminui, até que todos estejam ordenados;
Ordenação por inserção
Simulação da ordenação por inserção
V[1] V[2] V[3] V[4] V[5]
50 37 48 19 26
37 50 48 19 26
37 48 50 19 26
19 37 48 50 26
19 26 37 48 50
Ordenação por inserção
Analisando a ordenação por inserção vemos que o
número de comparações no pior caso é ½(n2 - n),
portanto sua complexidade e O(n2).
O número de comparações varia de n - 1, quando os
itens estão inicialmente em ordem crescente, a ½(n2 -
n) quando os itens estão inicialmente em ordem
decrescente.
Nos métodos baseados em troca e seleção, esse número é
fixo. Ou seja, em geral o método de inserção pode ser
um pouco mais eficiente que os outros dois.
Ordenação por inserção
Resumindo...
Ordena um vetor pela inserção de cada elemento em sua
posição correta;
Insertion sort
Implementação simples e fácil de compreender;
Divide o vetor em duas partições;
Baixa eficiência para ordenar muitos elementos;
Pode ser mais eficiente que a ordenação por troca e
por seleção.
Ordenação por intercalação
A operação de intercalação considera que um vetor
v[p..r] está dividido em duas partes v[p..q] e v[q+1,r]
ordenadas, mas, no todo, ele ainda não está ordenado;
A ideia é intercalar os itens dessas duas partes, de modo
a garantir que o vetor inteiro fique ordenado.
17 38 45 63 29 51 70 88
O vetor como um todo não está ordenado
1ª parte ordenada 2ª parte ordenada
q p r
Ordenação por intercalação
O algoritmo de ordenação por intercalação (Merge Sort)
utiliza o paradigma dividir e conquistar:
Dividir o problema em um determinado número de
subproblemas;
Conquistar os subproblemas, resolvendo-os recursivamente.
Porém, se os tamanhos dos subproblemas forem pequenos o
bastante, basta resolver os subproblemas de maneira direta;
Combinar as soluções dadas aos subproblemas, a fim de formar
a solução para o problema original.
Ordenação por intercalação
Intuitivamente, o merge sort usa o paradigma de dividir
e conquistar da seguinte maneira:
Dividir: divide a sequência de n elementos a serem ordenados
em duas subsequências de n/2 elementos cada uma.
Conquistar: classifica as duas subsequências recursivamente,
utilizando a ordenação por intercalação.
Combinar: faz a intercalação das duas sequências ordenadas, de
modo a produzir a resposta ordenada.
Ordenação por intercalação
Exemplo da ordenação por intercalação
Ordenação por intercalação
Ordenação por intercalação
Analisando a complexidade O tempo de execução do procedimento merge sort pode ser
representado pela seguinte relação de recorrência:
Ordenação por intercalação
Ordenação por intercalação
Ordenação por intercalação
Ordenação por intercalação
Resumindo...
Divide o vetor ao meio, recursivamente, até que o vetor fique
com um elemento e estes sejam ordenados e intercalados;
Utiliza a técnica da divisão e conquista;
É a menor complexidade para algoritmos de ordenação baseado
em comparação de itens. O método pode ser considerado
ótimo.
Merge sort
Ordenação quick sort
O algoritmo de ordenação rápida, quick sort, faz uso da
técnica da divisão e conquista da seguinte forma: Dividir: o vetor v[p..r] é particionado em dois subvetores não
vazios v[p..q] e v[q+1..r], tais que cada elemento de v[p..q] é
menor ou igual a cada elemento de v[q+1..r]. O índice q
(pivô) é calculado como parte do processo de particionamento.
Conquistar: os dois subvetores são ordenados por chamadas
recursivas ao quick sort.
Combinar: durante o processo recursivo, os elementos vão
sendo ordenados no próprio vetor.
Ordenação
quick sort
Ordenação quick sort
Analisando a complexidade
O procedimento partição compara todo os elementos do
vetor com o pivô, logo realizará O(n) comparações;
O tempo de execução do quick sort depende se o
particionamento é ou não balanceado. Se for balanceado é
tão rápido quanto o merge sort, caso contrário é tão lento
quanto o insertion sort.
Ordenação quick sort
Analisando a complexidade
No pior caso T(n) = T(n-1) + n
No melhor caso T(n) = 2T(n/2) + n
Ordenação quick sort
Analisando a complexidade do pior caso T(n) = T(n-1) + n
T(n) = (T(n-1-1)+n) + n = T(n-2)+2n
T(n) = ((T(n-1-1-1)+n) + n)+n = T(n-3)+3n
...
T(n) = T(n-i)+in
A recursão termina quando se atinge um vetor de
tamanho 1, assim temos T(n-i) = T(1), então:
n - i = 1
i = n - 1
Ordenação quick sort
Analisando a complexidade do pior caso Substituindo i por n -1, temos:
T(n) = T(n-i) + in =T(n-(n-1)) + (n-1)n = T(1) + (n-1)n = 1 + n2 - n
Portanto, no pior caso a complexidade do quick sort é:
O(n2)
n - i = 1
i = n - 1
Ordenação quick sort
Ordenação quick sort
Resumindo...
Assim como o merge sort, o quick sort se baseia no paradigma
de dividir e conquistar;
Escolhe-se um pivô e separam-se os elementos em 2 partes: os
elementos menores que o pivô ficam à esquerda e os maiores à
direita;
O processo é repetido recursivamente.
Ordenação heap sort
Baseado na estrutura de dados heap;
Inicialmente transforma o vetor a ser ordenado em um heap;
O primeiro elemento (maior) será trocado com o último,
ocupando sua posição definitiva;
Repete-se o processo até ordenar todos os elementos.
Qual o algoritmo mais eficiente?
Adaptado de Ascencio e Araújo, 2010
Qual o algoritmo mais eficiente?
Qual o algoritmo mais eficiente?
Adaptado de Ascencio e Araújo, 2010
Qual o algoritmo mais eficiente?
Qual o algoritmo mais eficiente?
Referências
OLIVEIRA, Ricardo de Souza; TAVEIRA, Gilda Aché;
BOTINI, Joana. Estruturas de Dados. Rio de Janeiro: Ed.
Senac Nacional, 1999.
PUGA, Sandra; RISSETTI, Gerson. Lógica de
programação e estruturas de dados, com aplicações
em Java. São Paulo: Pearson, 2009.
