Embed Size (px)
Citation preview
Ordenação - Motivação
Universidade Federal de Santa MariaColégio Agrícola de Frederico WestphalenCurso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
Algoritmos para ordenação de dados
• Requisito comum em aplicações: apresentar informações ordenadas;
• Alternativas:Manter os dados sempre ordenados (as inclusões são feitas mantendo-se a ordem desejada);
Alto custo computacional (pois a cada inclusão a informação precisa “descobrir” o seu lugar);Pouca flexibilidade (funciona apenas para um único critério de ordenação);
Aplicar algoritmos de ordenação em dados desordenados;Maior flexibilidade (diferentes critérios podem ser aplicados);
Sorting• Requisitos:
Eficácia de Tempo de execução (devem ser rápidos);Consumo de memória (devem ocupar pouca memória);
• AplicaçãoAlgoritmos de ordenação são normalmente aplicados em listas que possuem uma relação de vizinhança em todos os nodos: como listas duplamente encadeadas e vetores;
A entrada do algoritmo é um conjunto desordenado e a saída é o mesmo conjunto, porém ordenado.
• Quanto a localização dos dados:Interna – todos os registros cabem na mem. principal;Externa – os registros estão guardados em arquivos e precisam ser ordenados parcialmente em mem. principal;
• Quanto a estabilidadeEstáveis
Em uma reordenação (por outro campo) a ordem original não é alterada;
InstáveisSe uma reordenação ocorrer a ordem original pode ser alterada.
Ex. Suponhamos uma lista de nomes de pessoas e suas idades, ordenada alfabeticamente. Se uma método de ordenação for aplicado pelo campo idade o método estável consegue também manter a ordem alfabética nos
indivíduos de mesma idade enquanto que o método instável não (métodos instáveis geralmente são mais eficientes).
Aula 13 – Selection Sort
Universidade Federal de Santa MariaColégio Agrícola de Frederico WestphalenCurso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
Selection Sort• Ordenação por seleção;
• Algoritmo de simples implementação, recomendado para pequenos conjuntos de dados;
• Consiste em passar sempre o menor valor da lista para a primeira posição, depois, o de segundo menor valor para a segunda posição, e assim sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.
Selection Sort
• Algoritmo:procurar o menor elemento e trocar com o elemento na primeira posição;procurar o segundo menor elemento e trocar com o elemento na segunda posição;proceder assim até a ordenação estar completa.
• Implementação:Laços de repetição aninhados.
Selection Sort (simulação)Dados
originais
1ªIteração
2ªIteração
Selection Sort (simulação)
3ªIteração
4ªIteração
Neste caso não há troca
Algoritmo - Selection Sort
void selectionSort(int* vet, int tam) {
int i, j, min;
for (i = 0; i < (tam-1); i++) {min = i;
for (j = (i+1); j < tam; j++) {if(vet[j] < vet[min])
min = j;}
if (i != min) {troca(&vet[i],&vet[min]);
}}
}
Aula 14 – Insertion Sort
Universidade Federal de Santa MariaColégio Agrícola de Frederico WestphalenCurso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
Insertion Sort• Ordenação por inserção;
• Consiste em percorrer uma lista de elementos da esquerda para a direita e à medida em que se avança os elementos mais à esquerda vão sendo ordenados.
• É como se o elemento a ser analisado fosse ‘inserido’ no local correto da lista movimentando os demais elementos para a direita;
Insertion Sort
• Algoritmo:O insertion sort consiste em manter os i primeiros elementos ordenados entre si.
No passo i, insere o i+1 elemento na posição correta entre os i primeiros.No passo i+1, insere o i+2 elemento na posição correta entre os i+1primeiros.No passo i+2, insere o i+3 elemento na posição correta entre os i+2primeiros....
A inserção do item em uma posição adequada é realizada movendo-se as chaves maiores para a direita de forma a criar uma posição vazia.
Insertion Sort (simulação)Dados
originais
1ªIteração
2ªIteração
Insertion Sort (simulação)
3ªIteração
4ªIteração
Dados Ordenados
Algoritmo – Insertion Sort
void insertionSort(int* vet, int tam){
int i, j, chave;
for(j=1; j<tam; j++) {chave = vet[j];i = j-1;while(i >= 0 && vet[i] > chave) {
vet[i+1] = vet[i];i--;
}vet[i+1] = chave;
}}
Exercícios para fixação
• Que tal implementar uma aplicação para medir o tempo de execução de diferentes algoritmos de ordenação?
Experimente vetores de igual tamanho em diferentes ordens (já ordenados, ordem aleatório, ordem inversa);
Incremente essa aplicação ao longo das aulas incluindo todos os algoritmos estudados até então.
