Slide algoritmos de ordenação

Prévia do material em texto

Algoritmos de Ordenação 
Profº Carlos Alberto T. Batista 
E-mail: carlos.batista@facape.br 
 carlos36_batista@yahoo.com.br 
 
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. 
Exemplos_em_C/Ordenacao/BubbleSort.cpp
Exemplos_em_C/Ordenacao/BubbleSort.cpp
Exemplos_em_C/Ordenacao/BubbleSort.cpp
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. 
 
D:/Pascalzim510/pascalzim/Alg_de_Ordenação/selectionsort.pas
Ordenação por seleção 
 Resumindo... 
 
 Selection sort 
 
 Simples e de fácil entendimento; 
 
 Baixo desempenho para ordenar grandes quantidades 
de informações. 
D:/Pascalzim510/pascalzim/Alg_de_Ordenação/selectionsort.pas
D:/Pascalzim510/pascalzim/Alg_de_Ordenação/selectionsort.pas
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/SelectionSort.pas
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/SelectionSort.pas
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/SelectionSort.pas
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. 
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/InsertionSort.pas
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/InsertionSort.pas
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/InsertionSort.pas
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 
C:/Dev-Pas/MeusProjetos/Exemplos_ED_2016_1/Ordenação/MergeSort.pas
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 
recursivasao 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. 
 
D:/Pascalzim510/pascalzim/Alg_de_Ordenação/quicksort.pas
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.