Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Aula 04 – Limite assintótico para a ordenação, Ordenação em tempo linear MC3305 Algoritmos e Estruturas de Dados II Prof. Jesús P. Mena-Chalco jesus.mena@ufabc.edu.br 2Q-2014 2 Ordenação Ordenar corresponde ao processo de re-arranjar um conjunto de objetos em ordem ascendente ou descendente. O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado. Diversos algoritmos de ordenação já foram estudados e implementados... 3 Ordenação Os métodos de ordenação são classificados em 2 grande grupos: Ordenação Interna: Se o arquivo a ser ordenado cabe todo na memória principal Ordenação Externa: Se o arquivo a ser ordenado não cabe todo na memória principal 4 Ordenação Os métodos de ordenação são classificados em 2 grande grupos: Ordenação Interna: Se o arquivo a ser ordenado cabe todo na memória principal → Algoritmos Baseados em Comparações → Algoritmos Não Baseados em Comparações 5 Ordenação baseada em comparações 6 Ordenação Algoritmos basedos em Comparações Insertion sort Selection sort Bubble sort Merge sort Quick sort Complexidade computacional [limite matemático] [limite assintótico para a ordenação] 7 Ordenação baseada em comparações Sem perda de generalidade suponha que os valores a ser ordenados são sempre distintos [Árvore de decisão] 8 Ordenação baseada em comparações Sem perda de generalidade suponha que os valores a ser ordenados são sempre distintos [Árvore de decisão] [Cada nó folha está associada a uma permutação dos elementos do vetor] 9 Ordenação baseada em comparações Sem perda de generalidade suponha que os valores a ser ordenados são sempre distintos [Árvore de decisão] [Qualquer algoritmo de ordenação deverá percorrer um caminho desta árvore] da raiz até a folha 10 Ordenação baseada em comparações Sem perda de generalidade suponha que os valores a ser ordenados são sempre distintos [Árvore de decisão] [Qualquer algoritmo de ordenação deverá percorrer um caminho desta árvore] da raiz até a folha Número de folhas = n! 11 Ordenação baseada em comparações Seja L o número de folhas de uma árvore binária e h sua altura. Então h=3 L=8 12 Ordenação baseada em comparações Seja L o número de folhas de uma árvore binária e h sua altura. Então h=3 L=8 13 Ordenação baseada em comparações Seja L o número de folhas de uma árvore binária e h sua altura. Então h=3 L=8 14 Ordenação baseada em comparações Algoritmos basedo em Comparaçães Insertion sort Selection sort Bubble sort Merge sort Quick sort Vários algoritmos aqui listados são ótimos pois a sua complexidade computacional é 15 Ordenação em tempo linear 16 Ordenação Algoritmos basedo em Comparações Insertion sort Selection sort Bubble sort Merge sort Quick sort Algoritmos não baseados em Comparações (utilizam alguma informação sobre os dados) Counting sort Radix sort Bin sort / Bucket sort Algoritmos que fazem a ordenação em tempo linear 17 Counting sort Os elementos a serem ordenados são números inteiros “pequenos” Números inteiros todos menores ou iguais a k, 18 Counting sort Os elementos a serem ordenados são números inteiros “pequenos” Números inteiros todos menores ou iguais a k, Counting sort ordena estes n números em tempo Exemplo: → n = 1 000 000 → k = 30 19 Counting sort O algoritmo usa dois vetores auxiliares para ordenar A: C (de tamanho k), que guarda em C[i] o número de ocorrencias de elementos i em A. B (de tamanho n), onde se constroi o vetor ordenado. Simulação: https://www.cs.usfca.edu/~galles/visualization/CountingSort.html 20 Counting sort A C B 21 Counting sort A C B 22 Counting sort A C B 23 Counting sort A C B 24 Counting sort A C B 25 Counting sort A C B 26 Counting sort A C B 27 Counting sort A C B 28 Counting sort A C B 10 29 Counting sort A C B 10 16 30 Counting sort A C B 3010 31 Counting sort A C B 30 29 10 32 Counting sort Esboçe o algoritmo! (7 min) C (de tamanho k), que guarda em C[i] o número de ocorrencias de elementos i em A. B (de tamanho n), onde se constroi o vetor ordenado. 33 Counting sort 34 Counting sort 35 Counting sort 36 Counting sort M: número de movimentações de registros 37 Counting sort O Counting sort é um algoritmo que faz a ordenação de forma estável: A posição relativa de elementos iguais que ocorrem no vetor ordenado permanecem na mesma ordem em que aparecem na entrada. → Counting sort e Quick sort são estáveis → Heap sort não é estável. 38 Counting sort A C B 1010 39 Radix sort Ordena o vetor A de n números inteiros com um número constante d de digitos A ordem começa pelo digito menos significativo. Simulação: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html 40 Radix sort A complexidade computacional, considerando o número de movimentações de registros, e o counting sort: Counting sort = Merge sort = ← Vantajoso quando d<log(n) 41 Bucket sort (Ordenação por balde) Possui tempo linear, desde que os valores a serem ordenados sejam distribuídos uniformemente sobre o intervalo [0, 1). Divide o intervalo [0, 1) em n sub-intervalos iguais, denominados buckets (baldes), e então distribui os n números reais nos n buckets. Como a entrada é composta por dados distribuídos uniformemente, espera-se que cada balde possua, ao final deste processo, um número equivalente de elementos (usualmente 1). 42 Bucket sort (Ordenação por balde) 43 Bucket sort (Ordenação por balde) Cada elemento A[i] satisfaz 0 ≤ A[i] < 1. Para obter o resultado, basta ordenar os elementos em cada bucket e então apresentá-los em ordem Simulação: https://www.cs.usfca.edu/~galles/visualization/BucketSort.html 44 Atividade bônus: radixsort (7/julho - 23h50) Implemente o algoritmo Radix sort Esta atividade é valida para quem não enviou (não enviará) um Exercício-Programa. Os arquivos que deverá submeter pelo Tidia são: Código fonte em C/C++ (radixsort-RA.cpp) Um PDF contendo um exemplo de execução (radixsort-RA.pdf) Nota: o formato desse relatório é livre. Slide 1 Slide 2 Slide 3 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 32 Slide 33 Slide 34 Slide 36 Slide 37 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44
Compartilhar