PublicouCamila Sardinha Alterado mais de 3 anos atrás
Estrutura de Dados Algoritmos de Ordenação Registros (Estrutura de Dados Heterogêneas)
2 Visão Global O conceito de um conjunto ordenado de elementos tem considerável impacto sobre nossa vida cotidiana. Exemplos: Localizar um número telefônico em catálogo; Procurar um livro em biblioteca tradicional ou virtual; Saber qual o próximo documento a ser impresso pela impressora em um departamento da empresa; Saber qual o próximo processo a ser executado pelo processador de uma máquina qualquer; etc...
3 Introdução Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem. Em outras palavras, efetua sua ordenação completa ou parcial. Existem várias razões para se ordenar uma seqüência Uma delas é a possibilidade se acessar seus dados de modo mais eficiente. Além de permitir seu agrupamento em classes e ainda a atualização de arquivos seqüenciais 3
4 Algoritmos de ordenação
1- Bubble sort 2- Selection Sort 3 – Insertion Sort 4 - Quick sort (vocês já viram) 5 - Shell sort (Pesquisa do aluno) 6 -	Merge sort (Pesquisa do aluno) 7 - Radix sort (Pesquisa do aluno)
5 Bubble sort Compara dois elementos consecutivos de um vector e se o da esquerda é maior que o da direita trocam de posição. Quando existem trocas, os elementos maiores tendem a deslocar-se para a direita e os menores para a esquerda. 5
6 Exemplo – BubbleSort (1/3)
7 Exemplo – BubbleSort (2/3)
8 Exemplo – BubbleSort (3/3)
9 Bubble sort - Implmentação
private void bubblesort(int vetor[]) { int temp; boolean alterado = true; imprimir(vetor); while (alterado) { temp = 0; alterado = false; for (int j = 0; j < vetor.length - 1; j++) { if (vetor[j] > vetor[j + 1]) { temp = vetor[j + 1]; vetor[j + 1] = vetor[j]; vetor[j] = temp; alterado = true; } 9
10 Conclusões Os algoritmos de ordenação por bolha: → São muito simples
→ Eficazes apenas para uma pequena quantidade de dados. ■ Realiza um grande número de comparações pelo vetor para ser ordenado; 10
11 de Maio de 2006Listas e Ordenação1 Pedro Barahona DI/FCT/UNL Introdução aos Computadores e à Programação 2º Semestre 2005/2006.
1 TAD Fila com Prioridade -FCP ATAI. 2 TAD Fila com Prioridade (Priority Queue) TAD Fila com Prioridade armazena uma colecção de elementos com prioridade.